# Recurrence relation converting to explicit formula

Let $a_n = -2a_{n-1 }+ 15a_{n-2 }$ with initial conditions $a_1 = 10$ and $a_2 = 70$.

a)Write the first 5 terms of the recurrence relation.

b)Solve this recurrence relation.

c)Using the explicit formula you found in part b, evaluate $a_5$. You must show that you are using the equation from part b.

a.)$a_1 = 10$;

$a_2 = 70$;

$a_3 = -2(70) + 15(10) = -140 + 150 = 10$;

$a_4 = -2(10) + 15(70) = -20 + 1050 = 1030$;

$a_5 = -2(1030) + 15(10) = -2060 + 150 = -1910$;

b.) Using an Excel generator, I determined: root1 = -5, root2 = 3, u = 1, v = 5

I came up with the explicit formula: $a_n = 1 * (-5)n + 5 * (3)n$ , but this is where I get lost in the sauce. I tried solving for $a_5$ and came up with a number that I care not to share. So I must have gone wrong somewhere, but I just can't find it. Any help or guidance would be greatly appreciated.

• Your formula seems correct to me, and I get $a_5=-1910$ when I plug in $n=5$. Maybe you just miscomputed that number. – Greg Martin Mar 29 '14 at 2:48
• oh my gosh, thank you. I must be running on empty... – SolomonSky Mar 29 '14 at 3:04

Use generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, write the recurrence as: $$a_{n + 2} = - 2 a_{n + 1} + 15 a_n$$ Running the recurrence "backwards" gives $a_0 = 6$ (starting at index 0 is nicer all around). Multiply the recurrence by $z^n$, sum over $n \ge 0$, and recognize: \begin{align} \sum_{n \ge 0} a_{n + 1} z^n &= \frac{A(z) - a_0}{z} \\ \sum_{n \ge 0} a_{n + 2} z^n &= \frac{A(z) - a_0 - a_1 z}{z^2} \end{align} to get: $$\frac{A(z) - 6 - 10 z}{z^2} = - 2 \frac{A(z) - 6}{z} + 15 A(z)$$ Solving for $A(z)$, and writing as partial fractions, gives: $$A(z) = \frac{6 + 22 z}{1 + 2 z - 15 z^2} = \frac{1}{1 + 5 z} + \frac{5}{1 - 3 z}$$ Two geometric series: $$a_n = (-5)^n + 5 \cdot 3^n$$ This gives $a_5 = -1910$.