Solving a Linear Non-Homogeneous Recurrence 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$$
 A: 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.
A: 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.
