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?
 A: 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.
A: 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.
A: 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$.   
