Finding particular solution when solving recurrence relation

Question

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$

Answer 1

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

Answer 2

The short version is that if your right hand side is a product of a polynomial in $n$ of degree $k$ and an exponential, your first guess for a particular solution will be a product of a polynomial in $n$ of degree $k$ and an exponential with the same base. This may fail if the form you have assumed is annihilated by the recurrence operator; for instance, this will not work for solving $a_{n+1}=2a_n+2^n$. If this happens, you try raising the degree of the polynomial. So in my example you would assume a particular solution of $(An+B)2^n$.

This form has a chance from the start because if you take a linear recurrence with constant coefficients and substitute in a product of a polynomial and an exponential, you get a product of a polynomial and an exponential. So you at least get the right form in this situation. When you look a little more carefully, you find that except when the recurrence operator sends your form to zero, this approach really does work. Raising the degree "adds independent variables" enough to eventually get you away from the functions which your recurrence operator sends to zero.

Answer 3

when i need to find a particular solution of $$a_{n+2} = -4a_n + 8n2^n $$ find it easier to make a change of variable $$u_n = a_n 2^{-n}, a_n = 2^n u_n.$$ the recurrence relation for $u_n$ is simpler and is $$2^{n+2}u_{n+2}=-4\, 2^nu_n+8n2^n\to u_{n+2}=-u_n+2n.\tag 1$$ for $(1),$ i can try $$u_n = an + b \to a(n+ 2)+b=-an - b+2n $$ gives $$a = 1, b = -1, u_n = n - 1, a_n = 2^n(n-1).$$