Setting up a matrix from a recurrence relation to find diagonal matrix?

665 Views Asked by At

Considering the recurrence $F_n= F_{n−1}+3F_{n−2}−2F_{n−3}$ where $F_0=0$, $F_1=1$ and $F_2=2$, use diagonalization to find a closed form of the expression.

If the sequence is continued the numbers are $F_3=5,F_4=9,F_5=20,F_6=37...$

When putting into a sequence matrix would the matrix be in the format of

\begin{align*} \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} ? \end{align*}

1

There are 1 best solutions below

0
On

you want to set up a $3 \times 3$ transition matrix $A = \pmatrix{0 & 1 & 0\\0 & 0 & 1\\-2 & 3 & 1}$ that takes $\pmatrix{f_{n-3} \\ f_{n-2} \\f_{n-1}}$ to $\pmatrix{f_{n-2}\\f_{n-1} \\f_n}.$

once you find the three eigenvalues(hopefully distinct), you form $f_n = A \lambda_1^n + B\lambda_2^n + C\lambda_3^n$ the three initial conditions will fix the constants $A, B$ and $C.$