Solving non homogeneous recurrence relation I am having a hard time understanding these questions. I know I need to find the associated homogeneous recurrence relation first, then its characteristic equation. I cant figure out how to find the particular solution to the non homo recurrence relation though.
Ex: $$a_{n}= 4a_{n-1} + 4a_{n-2} + (n+1)2^n$$
My characteristic equation is $r^2-4r-4=0$ and $r=2(1+ \sqrt{2}), r=2(1- \sqrt{2})$. Next I need to guess some equation for my $f(n)=(n+1)2^n$ and plug it into the original to find some constants,, I am having the trouble here,, I dont understand how to come up with these guess equations.
I know the theorem that says the general solution (of the non homo recurrence relation) is the general solution of the associated recurrence relation + the particular solution:
$a_{n}=a_{n}^{(h)} + a_{n}^{(p)}$
So far I have $a_{n}=A2(1+ \sqrt{2})^n + B2(1- \sqrt{2})^n + a_{n}^{(p)}$
 A: Forget all this, use generating functions directly. Define $A(z) = \sum_{n \ge 0} a_n z^n$, write:
$$
a_{n + 2} = 4 a_{n + 1} + 4 a_n + 8 (n + 3) \cdot 2^n
$$
Multiply by $z^n$, sum over $n \ge 0$, recognize:
\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 2^n
  &= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - 2 z} \\
  &= \frac{2 z}{(1 - 2 z)^2}
\end{align}
and get:
$$
\frac{A(z) - a_0 - a_1 z}{z^2}
  = 4 \frac{A(z) - a_0}{z} + 4 A(z)
      + \frac{16 z}{(1 - 2 z)^2} + \frac{3}{1 - 2 z}
$$
This gives, written as partial fractions (partially):
$$
A(z)
  = \frac{1 - 2 a_0 - 2 (a_1 - 1) z}{2 (1 - 2 z^2)} +\frac{1}{2 (1 - 2 z)}
$$
The $(1 - 2 z)^{-1}$ gives rise to a $2^n$ in the solution, while you can write:
\begin{align}
\frac{1}{1 - 2 z^2}
  &= \sum_{n \ge 0} 2^n z^{2 n} \\
\frac{z}{1 - 2 z^2}
  &= \sum_{n \ge 0} 2^n z^{2 n + 1}
\end{align}
Thus you get expressions for even/odd indices. Or you could split that into partial fractions too, and mess with the resulting irrationals.
If you are simply interested in a particular solution, pick any easy values, like $a_0 = 0$ and $a_1 = 1$, and expand the above.
A: Make sure you have enough functions to span the non-homogeneous term. In this case, the non-homogeneous term is $n2^n + 2^n$, so I would guess $a_n^{(p)} = An2^n + B2^n$. The reason this is enough is because the space of functions spanned by $\{n2^n, 2^n\}$ is invariant under the next operation, and it intersects the space of homogeneous solutions only at $0$.
