Find a closed form for $f_n=f_{n-1}+2f_{n-2}, n\ge 3$

Question

i) find a suitable matrix $A \in M_{2,2}( \mathbb{Q})$ $ \left( \begin{array}{cc} f_{n} \\ f_{n-1} \end{array} \right) % = A \left( \begin{array}{cc} f_{n-1} \\ f_{n-2} \end{array} \right) $

at this point I used the recursion equation and I got the result that: $ A =\left( \begin{array}{cc} 1 & 2 \\ 1 & 0 \end{array} \right) $

ii) diagonalize the matrix $A$ which means that find a matrix $s \in GL_{2}(\mathbb{Q})$ so that $S^{-1}AS$ is a diagonal matrix.

I have calculated the eigenvalues and eigenvectors of matrix A as usual and I got that

$ S =\left( \begin{array}{cc} 2 & -1 \\ 1 & 1 \end{array} \right) $

iii) combining i) and ii) find a closed formel to calculate the value of $f_{n}$

at this point I have no clue how to show the last step iii) this is my findig to iii) $ \left( \begin{array}{cc} f_{n} \\ f_{n-1} \end{array} \right) % = A^n \left( \begin{array}{cc} f_{n-1} \\ f_{n-2} \end{array} \right) $

but how can I show that I have to put $A^n$ to the equation above?

thus

$ \left( \begin{array}{cc} f_{3} \\ f_{2} \end{array} \right) % = A^n \left( \begin{array}{cc} f_{2} \\ f_{1} \end{array} \right) $

is that correct?

Answer 1

You found that $S^{-1}AS=D$ where $D$ is diagonal, so that $A=SDS^{-1}$. That is, you've shown that $$\left( \begin{array}{cc} f_{n} \\ f_{n-1} \end{array} \right) % = SDS^{-1} \left( \begin{array}{cc} f_{n-1} \\ f_{n-2} \end{array} \right)$$ where $S$, and $D$ are known fixed matrices, that is, independent of $n$. Therefore, substituting again we get $$\left( \begin{array}{cc} f_{n} \\ f_{n-1} \end{array} \right) % = SDS^{-1} \left( \begin{array}{cc} f_{n-1} \\ f_{n-2} \end{array} \right) = SDS^{-1} SDS^{-1} \left( \begin{array}{cc} f_{n-2} \\ f_{n-3} \end{array} \right) = SD^2S^{-1} \left( \begin{array}{cc} f_{n-2} \\ f_{n-3} \end{array} \right)$$ and repeating the process $k$ times we get $$\left( \begin{array}{cc} f_{n} \\ f_{n-1} \end{array} \right) % = SD^kS^{-1} \left( \begin{array}{cc} f_{n-k} \\ f_{n-(k+1)} \end{array} \right)$$ so for $k=n-1$ we get $$\left( \begin{array}{cc} f_{n} \\ f_{n-1} \end{array} \right) % = SD^{n-1}S^{-1} \left( \begin{array}{cc} f_{1} \\ f_{0} \end{array} \right)$$ Now since $D$ is diagonal then you can easily find $D^{n-1}$, and so if you are given $f_1$ (are you?) then you get an explicit formula for $f_n$.

Answer 2

This is the Jacobsthal recursion with a solution

$$f_n=\frac{(2^n-(-1)^n)}{3}$$

for $f_{0,1}=0,1$. For a more general solution to $f_n=af_{n-1}+bf_{n-2}$ with arbitrary initial conditions, see here.