I have a question about how to find the particular solutions when trying to solve recurrence relations. For example, trying to solve
$$ a_{n+2} = -4a_n + 8n2^n $$
I begin with finding the roots in the characteristic polynomial associated with the homogeneous equation, so
$ r_1 = 2i $ and $r_2 = -2i. $
Then, because the roots are complex, the general solution is
$$ a_n^{(h)} = 2n\left(\alpha \cos\left(\frac{πn}{2}\right)+\beta \sin\left(\frac{πn}{2}\right)\right) $$
Now, my textbook suggests trying a function of the form
$$ (An+B)2^n $$
when trying to find the particular solution. I don't understand why and I have come across a couple of other examples which have made me equally confused as I am this time. Could anyone shed some light on the matter? Is there some sort of "abc-solution" for this?
Update:
Here is what the book tells me to do. Only I don't really understand how to use it in this example.
The book tells me this:
For the case of the nonhomogeneous second-order relation
$ a_n + C_1a_{n-1} + C_2a_{n-2} = kr^n $
where k is a constant, we find that
a) $ a_n^{(p)} = Ar^n $ for A a constant, if $r^n$ is not a solution of the associated homogeneous relation.
b)$ a_n^{(p)} = Bnr^n$ where B is a constant, if the general solution = $c_1r^n + c_2r_1^n$ where $r_1 \neq r$
c) $a_n^{(p)} = Cn^2r^2$ for C a constant, when the general solution = $(c_1 + c_2n)r^n$
Best Answer
To use GF you need to multiply both sides by $z^k$ for some variable $|z|<1$ and sum over k. A generating function is a function of the type $G(z) = \sum_{k=0}^{\infty} a_k z^k$, so the first term on RHS will be $-4 G(z)$ and so on.
Algebraically you need to get $G(z)$ on LHS and some function $\Phi(z)$ on RHS and equate coefficients of $z^n$. This will be your 'closed-form expression' for $a_n$.
EDIT: here's the equation. You `massage' LHS a bit to get $\frac{G(z) -a_0 -a_1 z}{z^2}$ and set $2z=s$ and $ S=\sum_{k=0}^{\infty} ks^k $ to get $$ G(z) -a_0 -a_1 z = -4 z^2 G(z) +8 z^2 S $$
now you need to follow my suggestions above to get what you need