Considering the recurrence $F_n=F_{n-1}+3F_{n-2}-3F_{n-3}$ where $F_0=0$, $F_1=1$ and $F_2=2$. Use diagonalization to find a closed form expression for $F_n$.
So I first continued the recurrence to find $F_3=5$, $F_4=8$, $F_5=17$ … etc
From this is I got a vector with three consecutive terms in the recurrence to be
$u_k = \begin{pmatrix} -3F_{n-3} \\ 3F_{n-2} \\ F_{n-1}\end{pmatrix}$
From here get a matrix $A$ from the terms of the recurrence:
$A = \begin{pmatrix} F_4 & F_3 & F_2 \\ F_3 & F_2 & F_1 \\ F_2 & F_1 & F_0 \end{pmatrix} =
\begin{pmatrix} 8 & 5 & 2 \\ 5 & 2 & 1 \\ 2 & 1 & 0 \end{pmatrix}$
Then the action of $A$ on $u_k$ would produce the $u_{k+1}$ term. [Correct me if I am wrong.]
So, $Au_k = \begin{pmatrix} 8 & 5 & 2 \\ 5 & 2 & 1 \\ 2 & 1 & 0 \end{pmatrix} \begin{pmatrix} -3F_{n-3} \\ 3F_{n-2} \\ F_{n-1}\end{pmatrix} =
\begin{pmatrix} -24F_{n-3} + 15F_{n-2} + 2F_{n-1} \\ -15F_{n-3} + 6F_{n-2} + F_{n-1} \\ -6F_{n-3} + 3F_{n-2} + 0 \end{pmatrix}$
Then $u_0 = \begin{pmatrix} 2 \\ 1 \\ 0 \end{pmatrix}$
From this point on I am unsure how to follow through with completing the problem. I have followed this Fibonacci Recurrence Problem – Most Helpful to figure out what to do next but have fallen short.
I see that the next step should be to find $\det(A – \lambda I)$ :
$0 = \det(A – \lambda I) = \begin{vmatrix} 8-\lambda & 5 & 2 \\ 5 & 2-\lambda & 1 \\ 2 & 1 & -\lambda \end{vmatrix}$
$=(8-\lambda)\begin{vmatrix} 2-\lambda & 1 \\ 1 & -\lambda\end{vmatrix} – 5\begin{vmatrix} 5 & 1 \\ 2 & -\lambda\end{vmatrix} + 2\begin{vmatrix} 5 & 2-\lambda \\ 2 & 1\end{vmatrix}$
$= (8-\lambda)(-2\lambda^2-1)-5(-5\lambda-2)+2(1+2\lambda)$
$= -16\lambda^{2}-8 + 2\lambda^3 + \lambda + 29\lambda + 12$
$= 2\lambda^3-16\lambda^2+30\lambda+4$
$= 2(\lambda^3-8\lambda^2+15\lambda+2)$
$= 2((\lambda-5)(\lambda-3)\lambda+2)$
From the source above, I can't figure out what the next steps should be? Can anyone help? Thanks!
Best Answer
Your matrix $A$ is not correct. It should represent the recurrence. You define $u_k = \begin{pmatrix} F_{k+2} \\ F_{k+1} \\ F_{k}\end{pmatrix}$ and the matrix $A$ is such that $u_{k+1}=Au_k$, so $A=\begin{pmatrix} 1 & 3 & -3 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}$ where the first line is the recurrence and the next two lower the past values. This is the matrix you want to diagonalize, and it has nice eigenvalues. You need to find a matrix $P$ such that $A=P^{-1}DP$ with $D$ diagonal. The diagonal entries of $D$ will be the eigenvalues of $A$ and the nice thing is that $A^n=P^{-1}D^nP$. Powers of a diagonal matrix are rather easier than a general matrix.