<s>[INST] Solve the following non-homogeneous recurrence relation: Find the solution to the following non-homogenous recurrence relation:
$a_{n+2} - 4a_{n+1} + 4a_{n} = 2^n$ for $a_0=1, a_1 = 2$.
I have found from the characteristic polynomial the general homogenous solution is:
$a_{n} = c_{1}2^n + c_{2}n2^n$ where $c_1, c_2$ are constants.
For the particular solution I think I should substitute $a_{n} = c_3n^22^n$ where $c_3$ is also a constant. However when I make that substitution I can't seem to solve the equation for $c_3$, can someone help please? Thanks 
 [/INST] Define $A(z) = \sum_{n \ge 0} a_n z^n$, multiply the recurrence by $z^n$ and add over $n \ge 0$. Recognize e.g.
\begin{align}
\sum_{n \ge 0} a_{n + k} z^k 
  &= \frac{A(z) - a_0 - a_1 z - \ldots - a_{k - 1} z^{k - 1}}{z^k} \\
\sum_{n \ge 0} 2^n z^n
  &= \frac{1}{1 - 2 z}
\end{align}
to get
$$
\frac{A(z) - 1 - 2 z}{z^2} - 4 \frac{A(z) - 1}{z} + 4 A(z)
  = \frac{1}{1 - 2 z}
$$
As partial fractions:
$$
A(z) = \frac{1}{4} (1 - 2 z)^{-3}
         - \frac{1}{2} (1 - 2 z)^{-2}
         + \frac{5}{4} (1 - 2 z)^{-1}
$$
Using the generalized binomial theorem you can read off the coefficients:
\begin{align}
a_n &= \frac{1}{4} \binom{-3}{n} (-2)^n
         - \frac{1}{2} \binom{-2}{n} (-2)^n
         + \frac{5}{4} \binom{-1}{n} (-2)^n \\
    &= \frac{1}{4} \binom{n + 3 - 1}{3 - 1} 2^n
         - \frac{1}{2} \binom{n + 2 - 1}{2 - 1} 2^n
         + \frac{5}{4} \binom{n + 1 - 1}{1 - 1} 2^n \\
    &= \frac{1}{4} \left(
                     \frac{(n + 2) (n + 1)}{2}
                       - 2 \frac{n + 1}{1}
                       + 5
                   \right) \cdot 2^n \\
    &= (n^2 - n + 8) \cdot 2^{n - 3}
\end{align}
</s>