Solve non-homogeneous linear recurrence I have the following recurrence $$a_n - 3a_{n-2} + 2a_{n-3} = 9 (-2)^n$$ with initial conditions $a_0 = 0, a_1 = 1, a_2 = 26$. I wish to find an explicit formula for $a_n$.
The characteristic polynomial for this recurrence is given by $\lambda(x) = x^3 - 3x + 2 = (x-1)^2 (x+2)$
Using a method I've been shown in class, I find
$$ \lambda(x) \cdot \Sigma{a_nx^n} = P(x) + 9 \cdot \Sigma{2^nx^n}$$
$$ \Sigma{a_nx^n} = \frac{P(x)}{\lambda(x)} + \frac{9}{\lambda(x) \cdot (1+2x)}$$
$$ \Sigma{a_nx^n} = \frac{P'(x)}{(x-1)^2(x+2)(1+2x)}$$
now this gives me a system of equations with 4 unknowns, and only 3 initial conditions with which to solve it. Clearly I've made a mistake somewhere.
I've also tried to use the lucky guess method, but I am still unable to solve this recurrence.
Can someone point out my error in the above approach, or give a push in the right direction using the "lucky guess" method?
 A: Looks to me like the homogeneous solution is $A n + B + C (-2)^n$.  (The $n$ comes from the fact that you have a double root at $x=1$.)  The particular solution may be a bit tricky because the "forcing" term is proportional to a homogeneous solution.  The solution here is to try $a_n^{(p)} = D n (-2)^n$.  Plugging this into the equation, we get
$$D n (-2)^n - \frac{3}{4} D (n-2) (-2)^n - \frac14 D (n-3) (-2)^n = 9 (-2)^n$$
Note that the terms in $n$ cancel and we get
$$[1+(3/2)+(3/4)]D = 9 \implies D = \frac{36}{13}$$
Now the general solution is
$$a_n = A n + B + C (-2)^n + \frac{36}{13} n (-2)^n$$
$A$, $B$, and $C$ may be found from the initial conditions, which I assume is not above your pay grade.
A: Ron proposed you a nice an direct method but let's use your classical method and show that (with more work) the generating function $\,A(x):=\sum_{n\ge 0}a_{n}x^n$ allow to conclude too :
$$\sum_{n\ge 0} \left(a_{n+3} - 3a_{n+1} + 2a_{n}\right)x^n = 9 \sum_{n\ge 0}(-2)^{n+3}x^n$$
$$\sum_{n\ge 0} a_{n+3}x^n - 3\sum_{n\ge 0}a_{n+1}x^n + 2\sum_{n\ge 0}a_{n}x^n = -72 \sum_{n\ge 0}(-2x)^n$$
$$\frac{A(x)-a_0-a_1x-a_2x^2}{x^3} - 3\frac{A(x)-a_0}x + 2\,A(x) = -72 \sum_{n\ge 0}(-2x)^n$$
$$(A(x)-a_0-a_1x-a_2x^2) - 3x^2(A(x)-a_0) + 2x^3\,A(x) = -\frac {72\,x^3}{1+2x}$$
$$(1-3x^2+2x^3)A(x)-a_0-a_1x+(3a_0-a_2)x^2 = -\frac {72\,x^3}{1+2x}$$
And I'll let you continue to get (it is homework after all and mere partial fractions evaluation ; the fact that there are four fractions is unimportant) :
$$\frac 5{3(1-x)}+\frac 1{(1-x)^2}-\frac{20}{3(1+2x)}+\frac 4{(1+2x)^2}$$
Expanding these terms in powers of $x$ (and remembering for example that the expansion of $\frac 1{(1-x)^2}$ is the expansion of the derivative of $\frac 1{1-x}$) should give you the four terms obtained with Ron's much nicer method.
