Recursive formula, eigenvalue problem

Question

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?

Answer 1

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}.$$

Answer 2

Note that $X_{n+1}-2 X_n = X_n - 2 X_{n-1} = \Delta = X_1 - 2 X_0$.

Hence $X_{n+1} = 2 X_n + \Delta$.

The general solution is $X_n = 2^n X_0 + \sum_{k=0}^{n-1} 2^{n-k-1} \Delta = 2^n X_0+(2^{n}-1)\Delta = 2^n(X_1-X_0)-X_1+2X_0$.