<s>[INST] Find a direct way to calculate recursive elements (simple problem with matrices) I nearly solved this question, I just need a hand with the last part since it is a bit confusing.
We are given the recursive sequences $\{a_n\}$ and $\{b_n\}$ like this:
$a_1=1$, $b_1=2$
$a_n=a_{n-1}+b_{n-1}$
$b_n=3b_{n-1}-a_{n-1}$
We are asked to find a direct way to find $a_n$ and $b_n$
Here is what I did:
$\begin{pmatrix} a_n \\b_n \end{pmatrix}= \begin{pmatrix} a_{n-1}+b_{n-1} \\ 3b_{n-1}-a_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ -1 & 3 \end{pmatrix} \begin{pmatrix} a_{n-1} \\ b_{n-1} \end{pmatrix} = ... = \begin{pmatrix} 1 & 1 \\ -1 & 3 \end{pmatrix}^{n-1} \begin{pmatrix} a_1 \\ b_1 \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ -1 & 3 \end{pmatrix}^{n-1} \begin{pmatrix} 1 \\ 2 \end{pmatrix}$
the problem is that the matrix $\begin{pmatrix} 1 & 1 \\ -1 & 3 \end{pmatrix}$ is not diagonlizable. it's jordan form however is $\begin{pmatrix} 2 & 1 \\ 0 & 2 \end{pmatrix}$, so overall, if $B_J$ is a jordan basis:
$(B_J\begin{pmatrix} 2 & 1 \\ 0 & 2 \end{pmatrix}B_J^{-1})^{n-1}\begin{pmatrix} 1 \\ 2 \end{pmatrix} =\begin{pmatrix} 2 & 1 \\ 0 & 2 \end{pmatrix}^{n-1}\begin{pmatrix} 1 \\2 \end{pmatrix} = \begin{pmatrix} a_n \\ b_n \end{pmatrix}$
but what now? How can we find $\begin{pmatrix} 2 & 1 \\ 0 & 2 \end{pmatrix}^{n-1}$??
 [/INST] Hint: Note that $\begin{pmatrix}2 & 1\\ 0 & 2 \end{pmatrix}=\begin{pmatrix}2 & 0\\ 0 & 2 \end{pmatrix}+\begin{pmatrix}0 & 1\\ 0 & 0 \end{pmatrix}$ and $\begin{pmatrix}2 & 0\\ 0 & 2 \end{pmatrix}\begin{pmatrix}0 & 1\\ 0 & 0\end{pmatrix}=\begin{pmatrix}0 & 1\\ 0 & 0\end{pmatrix}\begin{pmatrix}2 & 0\\ 0 & 2 \end{pmatrix}$, therefore you can use the binomial theorem.
Also note that $\begin{pmatrix}0 & 1\\ 0 & 0\end{pmatrix}^2=\begin{pmatrix}0 & 0\\ 0 & 0\end{pmatrix}$.
Alternatively compute the first few powers by hand, then conjecture (and prove by induction) that $$\forall k\in \mathbb N\left(\begin{pmatrix} 2 & 1\\0 & 2\end{pmatrix}^k=\begin{pmatrix} 2^k & k2^{k-1}\\0 & 2^k \end{pmatrix}\right).$$
</s>