Solving a Linear Non-Homogeneous Recurrence

Question

How can I solve the following recurrence?

$$a_n = 121a_{n-2} + 14400 n$$

I derived this:

$$\frac{1228}{11} (-11)^n + \frac{-4044}{11}11^n + 4800n$$

Answer 1

Clearly the odd-indexed terms aren't going to "interact" with the even-index terms, so let's look at the sequences $(a_{2n})_n$ and $(a_{2n+1})_n$. We have $a_{2n}=121a_{2(n-1)}+14400(2n)$ and $a_{2n+1}=121a_{2(n-1)+1}+14400(2n+1)$. Both these sequences can be put in a standard form:

$$a_{n}=p a_{n-1} + q n + r$$

So let's study that form of sequence. Here's a trick for solving recurrences: look at the successive differences. Do they follow any kind of simple law?

$$\delta_n=a_{n}-a_{n-1}=p a_{n-1} + q n + r-(p a_{n-2} + q (n-1) + r)=p\delta_{n-1}+q$$

From which we can obtain the closed form:

$$\delta_n=p^{n-1}\left(\delta_1+m\right)-m$$

Where $m=\frac{q}{p-1}$, as long as $p\neq1$, of course. But

$$a_n=a_0+\sum^{n}_{k=1}\delta_k=a_0+(\delta_1+m)\sum^{n}_{k=1}p^{k-1}-nm=a_0+(\delta_1+m)\frac{p^n - 1}{p-1} - nm$$

Just for the sake of writing out the complete closed form:

When $p\neq 1$, given $a_{n}=p a_{n-1} + q n + r$: $$a_n=a_0+\left((p-1)a_0+q+r+\frac{q}{p-1}\right)\frac{p^n - 1}{p-1} - \frac{nq}{p-1}$$

I tested the formula out on an example to be sure.

Answer 2

You have written a linear recurrence relation. The elements

$$a_0, a_2, a_4, a_6, \dots$$ and $$a_1, a_3, a_5, a_7, \dots$$

will constitute "separate" linear progressions. Solve them using your normal methods, which you seem to know how to do.