solving non-homogeneous recurrence relation

Question

solve the equation $a_n − 4a_{n−2} = −3n + 8$ for initial values $a_0=2, a_1=1$

I'm stuck on finding the particular solution for $a_n$. I tried using the form $a_n = C_1n + C_2$ but that gets me nowhere??

Answer 1

Use generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, rewrite the recurrence so there aren't subtractions in indices:

$$ a_{n + 2} - 4 a_n = - 3 n + 2 $$

Multiply the recurrence by $z^n$, sum over $n \ge 0$, and recognize some sums:

$$ \frac{A(z) - a_0 - a_1 z}{z^2} - 4 A(z) = - 3 \sum_{n \ge 0} n z^n + 2 \frac{1}{1 - z} $$

Note that:

$\begin{align} \sum_{n \ge 0} n z^n &= z \frac{\mathrm{d}}{\mathrm{d} z} \sum_{n \ge 0} z^n \\ &= \frac{z}{(1 - z)^2} \end{align}$

Plug this into the above with the initial values, and solve for $A(z)$:

$\begin{align} A(z) &= \frac{2 - 3 z + 2 z^2 - 4 z^3}{(1 - z)^2 (1 - 2 z) (1 + 2 z)} \\ &= \frac{1}{(1 - z)^2} - \frac{1}{1 - z} + \frac{1}{1 - 2 z} + \frac{1}{1 + 2 z} \end{align}$

Read off the coefficient for $z^n$, knowing that:

$$ (1 - z)^{-r} = \sum_{n \ge 0} (-1)^n \binom{-r}{n} z^n = \sum_{n \ge 0} \binom{n + r - 1}{r - 1} z^n $$

so:

$\begin{align} a_n &= [z^n] A(z) \\ &= (n + 1) - 1 + 2^n + (-2)^n \\ &= n + 2^n + (-2)^n \end{align}$