Solving non homogeneous recurrence relation

Question

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)}$

Answer 1

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.

Answer 2

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$.