Solve non-homogeneous linear recurrence

Question

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?

Answer 1

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.

Answer 2

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.