Find a closed form for $f_n=f_{n-1}+2f_{n-2}, n\ge 3$ 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?
 A: 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$.
A: 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.
