I tasked with solving the recurrence relation $a_n = 5a_{n-1} - 6a_{n-2}$ given the initial conditions $a_0 = 1, a_1 = 4$. I do not know how to begin here. However, I know that $$a_2 = 14,$$ $$a_3 = 46,$$ $$a_4 = 146,$$ $$a_5 = 454.$$ What is the pattern here?
Edit: I have explicit instructions to use generating functions, and then extract the coefficients using the GF.
On
If you want generating functions, define $A(z) = \sum_{n \ge 0} a_n z^n$, write:
$\begin{align*} a_{n + 2} &= 5 a_{n + 1} - 6 a_n \\ \sum_{n \ge 0} a_{n + 2} z^n &= 5 \sum_{n \ge 0} a_{n + 1} z^n - 6 \sum_{n \ge 0} a_n z^n \\ \frac{A(z) - a_0 - a_1 z}{z^2} &= 5 \frac{A(z) - a_0}{z} - 6 A(z) \end{align*}$
Use the values for $a_0, a_1$, solve as partial fractions:
$\begin{align*} A(z) &= \frac{2}{1 - 3 z} - \frac{1}{1 - 2 z} \\ a_n &= [z^n] A(z) \\ &= 2 \cdot 3^n - 2^n \end{align*}$
It seem that $a_{n+1}= 3a_n$ for $n\geq 1$ and thus the sequance is geometric....
Prove by induction: Base $n=1,2$ is obivuosly.
Induction step: $n,n-1\to n+1$:
$$ a_{n+1} = 5a_n-6a_{n-1} = 15a_{n-1}-18a_{n-2} = 3(5a_{n-1}-6a_{n-2})= 3a_n$$