# Use eigenvalues to find formula for recurrence relation

(1) Sequence $$\{a_n\}$$ is defined as $$a_{0} = a_1 = a_2 = 1$$ and

$$a_n = 7a_{n-2} + 6a_{n-3}, for. \ n \geq 3$$.

Find a general formula for $$a_n$$

I have only solved recurrence relations for n >= 2 so far in my class, I am not sure as to how I should extend it to n >= 3?

Edit: P =

(2) $$C = \begin{pmatrix} 2 &2 & 0 \\ -1 & -1 & 0 \\ 2 & 2 & 3 \end{pmatrix}\$$. Diagonalise the matrix in 3 ways so that the diagonal matrices $$D_1, D_2, D_3$$ are different. I found it's eigenvalues to be

$$\lambda_1 = 0,$$ corresponding vector is $$(-1,1,0)$$.

$$\lambda_2 = 1,$$ corresponding vector is $$(-2,1,1)$$

$$\lambda_3 = 3,$$ corresponding vector is $$(0,0,1)$$

Is it correct to say that $$D_1 = \begin{pmatrix} 3 &0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{pmatrix}\$$. $$D_2 = \begin{pmatrix} 1 &0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 0 \end{pmatrix}\$$ $$D_1 = \begin{pmatrix} 3 &0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}\$$?

– lhf
Nov 6 '20 at 13:47

Hint for (1): We have $$\begin{pmatrix} a_n \\ a_{n-1} \\ a_{n-2} \end{pmatrix} = \begin{pmatrix} 0 &7 & 6 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix} \begin{pmatrix} a_{n-1} \\ a_{n-2} \\ a_{n-3} \end{pmatrix}$$ whose characteristic polynomial is $$x^3 - 7 x - 6$$ (no surprises here).

Finally, $$x^3 - 7 x - 6=(x + 1) (x + 2) (x - 3)$$.

• Thanks, I found the matrix P(edit in the qn) that diagonalizes A, but do I have to find the inverse of P directly in order to find $a_n$?
– foc
Nov 6 '20 at 14:31
• @foc, not really. Once you know the eigenvalues, you know that $a_n = c_1 \lambda_1^n + c_2 \lambda_2^n + c_3 \lambda_3^n$ and you can find $c_1,c_2,c_3$ from the initial conditions.
– lhf
Nov 6 '20 at 14:43
• @foc, check your work on $P$ at WA
– lhf
Nov 6 '20 at 14:45