I need some help solving the following recurrence relation:
$a_n = 4a_{n-1} - 4a_{n-2} + (n+1)*2^n$
What I've tried:
a) Find the general solution of the associated linear homogenous recurrence relation.
I got this general solution : $a^{(H)}_n = \alpha_1*2^n + \alpha_2*n*2^n $
b) Guess the particular solution.
This is the step I'm confused in. Seeing some other examples, I believe a correct guess would be $n^2*(p_1*n + p_0)*2^n$.
To get all the solutions I would have to put this particular solution equation into the original recurrence relation. This way I get a very complex equation. I think either I'm doing this incorrectly or I'm making it too complicated. Is there a better and more intuitive way to solve such recurrence relations?
Use generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, write the recurrence as: $$ a_{n + 2} = 4 a_{n + 1} - 4 a_n + 4 (n + 3) \cdot 2^n $$ Multiply the recurrence by $z^n$, add over $n \ge 0$, and recognize the sums: \begin{align} \sum_{n \ge 0} a_{n + r} z^n &= \frac{A(z) - a_0 - a_1 z - \ldots - a_{r - 1} z^{r - 1}}{z^r} \\ \sum_{n \ge 0} 2^n z^n &= \frac{1}{1 - 2 z} \\ \sum_{n \ge 0} n \cdot 2^n z^n &= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - 2 z} \\ &= \frac{2 z}{(1 - 2 z)^2} \end{align} Thus: $$ \frac{A(z) - a_0 - a_1 z}{z^2} = 4 \frac{A(z) - a_0}{z} - 4 A(z) + 4 \frac{2 z}{(1 - 2 z)^2} + 12 \frac{1}{1 - 2 z} $$ Written as partial fractions: $$ A(z) = \frac{4 + 4 a_0 - a_1}{2 (1 - 2 z)} - \frac{6 + 2 a_0 - a_1}{2 (1 - 2 z)^2} + \frac{1}{(1 - 2 z)^4} $$ Use of the generalized binomial theorem, in particular: $$ (1 - u)^{-m} = \sum_{k \ge 0} (-1)^k \binom{-m}{k} u^k = \sum_{k \ge 0} \binom{k + m - 1}{m - 1} u^k $$ and the fact that $\binom{k + m - 1}{m - 1}$ is a polynomial of degree $m - 1$ in $k$ finishes this off.