# combinatorics - recurrence relations

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.

• Start by assuming that a solution is of the form $a_n=r^n$ for some $r \in \Bbb{R}$. Then use that to get a quadratic equation in $r$. – Anurag A Apr 7 '19 at 20:36

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$$

• Yey, I go over 50K – Aqua Apr 7 '19 at 20:41
• Could you please explain how you wrote $5a_n - 6a_{n-1}=15a_{n-1}-18a_{n-2}$? – s0ulr3aper07 Apr 7 '19 at 21:04
• by induction hypothetis $a_n = 3a_{n-1}$ and $a_{n-1}=3a_{n-2}$ – Aqua Apr 7 '19 at 21:05
• This is of no help to you? – Aqua Apr 7 '19 at 21:39
• @MariaMazur It might be worth checking the OP's edit. It seems he forgot one restriction of the problem: he needs to use generating functions to solve this (probably a textbook exercise). :( – Eevee Trainer Apr 7 '19 at 23:41

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*}