How to find the nth term of a linear recurrence using matrices? 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$?
 A: 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$
