# Recurrence relation and deriving generating function

Let the sequence an be given by the recurrence relation

$$a_n = −2a_{n−1} + 8a_{n−2}$$ $$a_0 = 1, a_1 = 5$$

(a) Calculate $a_2, a_3$ and $a_4$.

(b) Derive an exact expression for the generating function of the sequence

$$A(x) = \sum_{n=0}^∞ a_nx^n$$

as a ratio of two polynomials.

(c) Use a partial fraction expansion of $A(x)$ to derive an exact expression for $a_n$.

I think I have some understanding of what I need to do but I am not completely sure.

(a) $a_2 = -2a_1+8a_0 = (-2)*5 + 8 = -2$

$a_3 = -2a_2+8a_1 = (-2)*(-2) + 8*5 = 44$

$a_4 = -2a_3+8a_2 = (-2)*44+8*(-2) = -104$

(b) Rearranging the relation we get

$a_n + 2a_{n−1} - 8a_{n−2} = 0$

Let $A = 1+5x-2x^2+44x^3-104x^4...$

then $2xA=2x+10x^2-4x^3+88x^4...$

and $-8x^2A=-8x^2-40x^3+16x^4...$

Adding the 3 up we get:

$(1+2x-8x^2)A = 1+7x$

Since all the cubic and higher terms are canceled out.

Hence, $$A = \frac{1+7x}{1+2x-8x^2}$$

I dont know about (c), but does this look ok?

• Judging from the first 100 terms (via Mathematica) the generating function you've obtained is correct. So now all you need to do is to find the closed-form expression. – Semiclassical Sep 13 '15 at 5:51
• Hint: $$\frac{1+7x}{1+2x-8x^2}=\frac{u}{1-ax}+\frac{v}{1+bx}$$ – Did Sep 13 '15 at 6:08

Now write $A = c_1/(1-2x) + c_2/(1+4x)$ with some $c_1$ and $c_2$ to derive the closed form. Alternatively, from this decomposition you know that $a_n = c_12^n + c_2(-4)^n$, so you can find $c_1$ and $c_2$ from plugging some values of $n$ in.