The recurrence relation is: $$A_{n} = 4A_{n-1} - A_{n-2} - 2A_{n}-3$$ $A_0=1 $ and $ A_1=1$ are given and I computed $A_3=6$, $A_3=21$, and $A_4=76$ using the recurrence formula. How can I use matrices to express the relationship between the terms? Let A be the matrix needed and b be the vector containing the base cases. We want this equation to be satisfied:
$$A^2b = z$$
Where z contains $A_(n+1)$. Give A, b and show that $A^2b$ contains $A_3$.
So far, I have A as: $$ \begin{matrix} 4 & -1 & -2 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \\ \end{matrix} $$
b as: $$ \begin{matrix} A_{n-1}\\ A_{n-2}\\ A_{n-3}\\ \end{matrix} $$
and z as: $$ \begin{matrix} 4A_{n-1}-A_{n-2}-2A_{n-3}\\ A_{n-1}\\ A_{n-2}\\ \end{matrix} $$
I'm very skeptical about this answer I got since I'm not entirely sure with what I'm doing because I don't know if my z contains $A_{n+1}$ Did I get those right, and if I did, where do I go from here? How do I show that $A^2b$ contains $A_3$?
Call $\color{blue}{y_n = A_n - 1}$, so that $A_n = y_n + 1$, so that the recurrence relation becomes
\begin{eqnarray} 3(y_n + 1) &=& 4(y_{n-1} + 1) - (y_{n-2} + 1) - 3 \\ \Rightarrow~~~ 3y_n &=& 4y_{n-1} - y_{n-2} \\ \Rightarrow~~~ y_n&=& \frac{4}{3}y_{n-1} - \frac{1}{3}y_{n/2} \end{eqnarray}
Call
$$ x_n = \pmatrix{y_n \\ y_{n - 1}} = \pmatrix{4/3 & -1/3 \\ 1 & 0} \pmatrix{y_{n-1} \\ y_{n-2}} = B x_{n-1} \tag{1} $$
So that
\begin{eqnarray} x_1 &=& B x_0 \\ x_2 &=& B x_1 = B(B x_0) = B^2 x_0\\ &\vdots&\\ x_n &=& B^n x_0 \tag{2} \end{eqnarray}
The problem is reduced to finding $B^n$, but that one is easy if the matrix is diagonalizable, which in your case happens to be the case. The eigenvalues are $\lambda = (1, 1/3)$, you can then write $B$ as
$$ B = U \Lambda U^{-1} = U \pmatrix{1 & 0 \\ 0 & 1/3} U^{-1} \tag{3} $$
$U$ is the matrix formed with the eigenvectors of $B$. $B^n$ is just
\begin{eqnarray} B^n = (U \Lambda U^{-1})^n = U\Lambda^n U^{-1} &=& U \pmatrix{1 & 0 \\ 0 & 1/3^n} U^{-1} \tag{4} \end{eqnarray}
Replace this into Eq (4), and you will get $x_n$ and from this $y_n$ and from this $A_n$