<s>[INST] Recursive formula, eigenvalue problem A sequence $ \{X_i \}_{i \geq 0} $ is defined recursive by $ X_{n+1} = 3 X_{n} - 2X_{n-1}, \qquad n \geq1. $ 
and $ X_0 = \begin{pmatrix}
1 & 0  \newline
1 & 1 
\end{pmatrix},X_1 = \begin{pmatrix}
1 & 1  \newline
1 & 1 
\end{pmatrix}. $ Find an explicit formula for $ X_n $.
My attempt;
We can write $  = \begin{pmatrix}
X_{n+1}   \newline X_{n} \end{pmatrix} = \begin{pmatrix} 3 & -2  \newline 1 & 0 \end{pmatrix} \begin{pmatrix} X_{n} \newline X_{n-1} \end{pmatrix} $ for $ n \geq 1. $ Diagonalizing the matrix yields 
$\begin{pmatrix} X_{n+1}   \newline X_{n} \end{pmatrix} = \begin{pmatrix} 2 & 1  \newline 1 & 1 \end{pmatrix} \begin{pmatrix} 2^n & 0  \newline 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & -1  \newline -1 & 2 \end{pmatrix} \begin{pmatrix} X_{n} \newline X_{n-1} \end{pmatrix}$
This is and old exam; now the answer concludes that $X_n $ can be written as $ X_n = A + 2^n B $, for some matrices A and  B, which can be found by plugging in $ X_1 $ and $ X_0.$ My question is how did he draw this conclusion, is it only from the eigenvalues? How would one approach questions on this form if the matrix couldnt be diagonalized?
 [/INST] We may prove the claim $X_n = A + 2^n B$ by induction. The inductive step is easy: for $n\geq 1$,
$$X_{n+1} = 3 X_{n} - 2X_{n-1}=3(A + 2^n B)-2(A + 2^{n-1} B)=A + 2^{n+1} B.$$
It remains to find $A$ and $B$ by considering the cases $n=0$ and $n=1$:
$$\begin{cases}
X_0=A + B\\
X_1=A + 2 B
\end{cases}\implies \begin{cases}
B=X_1-X_0\\
A=X_0-B=2X_0-X_1
\end{cases}.$$
</s>