Finding the general formula of the sequence $ a_n = 7a_{n-2} + 6a_{n-3} $

Question

Given the equation $ a_n = 7a_{n-2} + 6a_{n-3} $, and $ a_0 = a_1 = a_2 = 1 $, how do I find the general equation?

I have tried to express this sequence in matrix form, $ Q = Xb $ as follows

$$ Q = \begin{bmatrix} a_{n+1} \\ a_{n-2} \\ a_{n-3} \\ \end{bmatrix} \hspace{1cm} X =\begin{bmatrix}0 & 7 & 6 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} \hspace{1cm} b = \begin{bmatrix} a_{n} \\ a_{n-1} \\ a_{n-2} \\ \end{bmatrix} $$

I attempt diagonalize $X$ in order to find $X^n$, but the eigenvalues of $X$ seem to be not real

Can anyone see if my method is correct?

Answer 1

Try instead $$Q = A_n=\begin{bmatrix} a_{n} \\ a_{n-1} \\ a_{n-2} \\ \end{bmatrix} \hspace{1cm} X =\begin{bmatrix} 0&7 & 6 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{bmatrix} \hspace{1cm} b = A_{n-1}=\begin{bmatrix} a_{n-1} \\ a_{n-2} \\ a_{n-3} \end{bmatrix}$$

Hence $A_n=X^n A_0=X^{n-3}A_3$

The matrix $X$ can be diagonalized as

$$ X = \begin{bmatrix} 9&4 & 1 \\ 3 & -2 & -1 \\1 & 1 & 1 \\ \end{bmatrix} \begin{bmatrix} 3&0 & 0 \\ 0 & -2 &0 \\0 & 0 & -1 \\ \end{bmatrix} \frac{1}{20}\begin{bmatrix} 1&3 & 2 \\ 4 & -8 &-12 \\-5 & 5 & -30 \\ \end{bmatrix} $$

Answer 2

Hint: This is a linear recurrence equation. Use the ansatz $a_n=A^n$. This will lead you to a cubic polynomial:

$$A^3=7A+6.$$ It has 3 roots ($A_1,A_2,A_3$), which you can calculate by hand (Cardano formula), or by polynomial long division (hint: $A=-1$ is a solution/root), or by using wolfram alpha.

Then the general solution is: $$a_n=c_1A_1^n+c_2A_2^n+c_3A_3^n.$$

Determine $c_1,c_2$ and $c_3$ by your initial conditions.

Answer 3

We have $a_n = 7a_{n-2}+6a_{n-3}$ and we can write:

\begin{align} a_n &= 0a_{n-1}+7a_{n-2}+6a_{n-3}\\ a_{n-1} &= 1a_{n-1} + 0a_{n-2} +0a_{n-3}\\ a_{n-2} &= 0a_{n-1}+1a_{n-2}+0a_{n-3} \end{align}

Setting

$$A = \begin{pmatrix} 0 & 7 & 6\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{pmatrix}\ \text{and}\ \ x_n = \begin{pmatrix} a_n\\ a_{n-1}\\ a_{n-2}\end{pmatrix}$$

we get that $$x_n = Ax_{n-1} = A^2x_{n-2} =\ldots = A^{n-2}x_2$$

Eigenvalues of $A$ are $\{-1,-2,3\}$ with corresponding eigenvectors $(1,-1,1), (4,-2,1), (9,3,1)$. Can you finish from here?

Another way to do this is using generating functions. Let $f(x) = \sum_{n=0}^\infty a_nx^n$. We have that $a_n = 7a_{n-2}+6a_{n-3}$ and we can multiply it by $x^n$ and sum it for all $n\geq 3$ to get

\begin{align}&\sum_{n=3}^\infty a_nx^n = 7\sum_{n=3}^\infty a_{n-2}x^n + 6\sum_{n=3}^\infty a_{n-3}x^n\\ \implies &\sum_{n=3}^\infty a_nx^n = 7x^2\sum_{n=1}^\infty a_nx^n + 6x^3\sum_{n=0}^\infty a_nx^n\\ \implies &f(x) -a_2x^2-a_1x-a_0 = 7x^2(f(x)-a_0)+6x^3f(x)\\ \implies &f(x)=\frac{1+x-6x^2}{1-7x^2-6x^3}\\ \implies &f(x)=\frac 32\cdot\frac 1{1+x} -\frac 45\cdot\frac 1{1+2x}+\frac 3{10}\frac 1{1-3x}\\ \implies &f(x) = \frac 32\sum_{n=0}^\infty (-1)^nx^n-\frac 45\sum_{n=0}^\infty (-2)^nx^n+\frac 3{10}\sum_{n=0}^\infty 3^nx^n\\ \implies &f(x) = \sum_{n=0}^\infty \left(\frac 32(-1)^n-\frac 45(-2)^n + \frac 3{10}\cdot 3^n\right)x^n\\ \implies &a_n = (-1)^n\left(\frac 32 -\frac{2^{n+2}}5\right)+\frac{3^{n+1}}{10} \end{align}