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!
 A: 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
$$
A: 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$.
