# 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} (-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.
If you guess that $$a_n = (p_3 n^3 + p_2 n^2 + p_1 n + p_0)2^n$$ is a solution for the recurrence, then solve this linear system for $$p_3,p_2,p_1,p_0$$ in terms of $$a_0$$ and $$a_1$$: $$\begin{eqnarray} a_0 &=& (p_3 0^3 + p_2 0^2 + p_1 0 + p_0) 2^0 \\ a_1 &=& (p_3 1^3 + p_2 1^2 + p_1 1 + p_0) 2^1 \\ a_2 &=& (p_3 2^3 + p_2 2^2 + p_1 2 + p_0) 2^2 \\ a_3 &=& (p_3 3^3 + p_2 3^2 + p_1 3 + p_0) 2^3 \\ a_2 &=& 4 a_1 -4 a_0 + (2+1)2^2 \\ a_3 &=& 4 a_2 -4 a_1 + (3+1)2^3 \\ \end{eqnarray}$$ This gives $$a_n = \frac16\left( n^3 + 6n^2 + (3a_1 - 6 a_0 -7)n + 6a_0 \right)2^n$$ which you can check is indeed a solution for the recurrence.
This difference equation is tricky. Denote by $$a_n^o$$ the solution to the homogeneous part: $$a_n^o-4a_{n-1}^o+4a_{n-2}^o=0$$. The characteristic polynomial associated to this equation is $$p(z)=z^2-4z+4$$ and $$p$$ has two identical roots: $$z_1=z_2=2$$, so the general solution to the homogeneous equation is $$a_n^o = (p+qn)2^n.$$ Unfortunately the forcing term in the inhomogeneous equation is exactly of the kind $$(p+qn)2^n$$, so we have to look for a solution of the kind $$a_n=(sn^3+rn^2+qn+p)2^n$$. In fact we can neglect the term $$(qn+p)2^n$$, since it solves the homogeneous equation. Now we put the ansatz $$a_n=(sn^3+rn^2)2^n$$ in the original inhomogeneous equation: $$L_n=a_n-4a_{n-1}+4a_{n-2}=(sn^3+rn^2)2^n-4(s(n-1)^3+r(n-1)^2)2^{n-1}+4(s(n-2)^3+r(n-2)^2)2^{n-2};$$ eventually we can determine the unknown coefficients $$r$$,$$s$$ by forcing $$L_n$$ to be equal to $$(n+1)2^n$$. We get $$L_n=[s(6n-6)+2r]2^n=(n+1)2^n$$, hence $$6s=1$$ and $$-6s+2r=1$$ which yield $$s=\frac{1}{6}$$ and $$r=1$$.