# Finding the solution to this specific recurrence relation

What would be the solution to $a_n = 7a_{n−2} + 6a_{n−3}$ with $a_0 = 9$, $a_1 = 10$, and $a_2 = 32$

I can find it for a specific value of (n), but not for just a general solution. Thanks!

• Still open for a non-generating function answer! – tekman22 Apr 15 '13 at 16:59
• Ok, done. :) The generating function approach requires solving exactly the same characteristic function, but its advantage is apparently that you don't have to solve a system of equations to account for the initial conditions. – ShreevatsaR Apr 15 '13 at 17:04
• @ShreevatsaR just want to make sure that these two answers don't contradict each other - mind giving this a look? gyazo.com/bf0f0684693bcb9a2b3fb7c1590beeb9 Thanks! – tekman22 Apr 15 '13 at 17:10
• I've replied to the comment on my answer: that linked image is wrong. – ShreevatsaR Apr 15 '13 at 17:15

By the general theory of such linear recurrence relations, the solutions to $a_n = 7a_{n-2} + 6a_{n-3}$ will all be of the form $a_n = c_1 r_1^n + c_2r_2^n + c_3r_3^n$, where $r_1, r_2, r_3$ are all solutions to $r^n = 7r^{n-2} + 6r^{n-3}$, i.e. to $r^3 = 7r + 6$. This is called the characteristic equation.

It turns out (or you can find by trial and error) that the solutions to the characteristic equation are $-1$, $-2$, and $3$.

So we have $a_n = c_1(-1)^n + c_2(-2)^n + c_33^n$. Putting your initial conditions given, namely $a_0 = 9$, $a_1 = 10$, and $a_2 = 32$, we get the equations

\begin{aligned} c_1 + c_2 + c_3 &= 9 \\ -c_1 - 2c_2 + 3c_3 &= 10 \\ c_1 + 4c_2 + 9c_3 &= 32 \end{aligned} solving which gives $c_1 = 8$, $c_2 = -3$, and $c_3 = 4$. So $a_n = 8(-1)^n - 3(-2)^n + 4(3)^n$.

• Hmm..are you sure this is right? – tekman22 Apr 15 '13 at 17:08
• This seems to contradict this method: gyazo.com/bf0f0684693bcb9a2b3fb7c1590beeb9 – tekman22 Apr 15 '13 at 17:08
• @jtm22: Yes I'm sure this is right. Just put $n = 3$ to check: the recurrence relation $a_n = 7a_{n-2} + 6a_{n-3}$ gives $a_3 = 7a_1 + 6a_0 = 7(10) + 6(9) = 124$. My expression $a_n = 8(-1)^n - 3(-2)^n + 4(3)^n$ gives $a_3 = -8 - 3(-8) + 4(27) = 124$, while the linked (wrong) solution $a_n = 3 + 5(2^n) + (-3)^n$ gives $a_3 = 3 + 5(8) + (-27) = 16$, which is wrong. – ShreevatsaR Apr 15 '13 at 17:14
• Makes sense. Thank you! – tekman22 Apr 15 '13 at 17:15
• I just checked it with a spreadsheet and it solves the problem correctly. – Ross Millikan Apr 15 '13 at 17:19

Use generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, and write the recurrence as: $$a_{n + 3} = 7 a_{n + 1} + 6 a_n \quad a_0 = 9, a_1 = 10, a_2 = 32$$ By properties of ordinary generating funtions: $$\frac{A(z) - a_0 - a_1 z - a_2 z^2}{z^3} = \frac{A(z) - a_0}{z} + 6 A(z)$$ Writing as partial fractions: $$A(z) = 4 \cdot \frac{1}{1 - 3 z} - 3 \cdot \frac{1}{1 + 2 z} + 8 \cdot \frac{1}{1 + z}$$ Expanding the various geometric series: $$a_n = 4 \cdot 3^n - 3 \cdot (-2)^n + 8 \cdot (-1)^n$$

• I am not familiar with generating functions, although you seem to live by them vonbrand! Haha, could we use another way possibly? – tekman22 Apr 15 '13 at 16:53
• @jtm22, there certainly are other ways. This is just by far the simplest. – vonbrand Apr 15 '13 at 16:54
• What is the characteristic equation? – tekman22 Apr 15 '13 at 16:54
• @jtm22, $(1 - 3 z) (1 + 2 z) (1 + z)$ – vonbrand Apr 15 '13 at 16:56
• Thanks. You wouldn't mind solving it with regular characteristic equations, though, would you? – tekman22 Apr 15 '13 at 16:59