# Recurrence Relation all general solutions

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?

• You are on the right track, and your method should work. There should be a lot of cancellations in your "complex equation" if you do the algebra right. Keep at it! – Gerry Myerson May 5 '14 at 12:47

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} \binom{-m}{k} u^k = \sum_{k \ge 0} \binom{k + m - 1}{m - 1} z^k$$ and the fact that $\binom{k + m - 1}{m - 1}$ is a polynomial of degree $m - 1$ in $k$ finishes this off.