Can I solve other recurrence relations with linear algebra than just Fibonacci sequence? Fibonacci sequence is defined by $\phi_{n+2} = \phi_n+\phi_{n+1}$ with $\phi_0 =0$ and $\phi_1 = 1$. I saw a proof of explicit form of $\phi_n$ that uses matrices and diagonalisation : $$\begin{bmatrix}\phi_{n+2}\\\phi_{n+1}\end{bmatrix} = A\begin{bmatrix}\phi_{n+1}\\\phi_{n}\end{bmatrix} = A^n\begin{bmatrix}1\\0\end{bmatrix}$$ Then we find $A$ from first equality and from second equality we Binet's formula.
I wonder if this technique can be used to solve other recurrence relations like 1, 2 and 3. I tried this method for 2, but I got a non-diagonalisable matrix; I did the following :
$$\begin{bmatrix}F(n+2)\\F(n+1)\\F(n) \end{bmatrix} = A\begin{bmatrix}F(n+1)\\F(n)\\1 \end{bmatrix} = A^n\begin{bmatrix}2\\4\\1 \end{bmatrix}$$
I got $$A = \begin{bmatrix}4&-3&+16\\1&0&0\\0&1&0\end{bmatrix}$$ which is not diagonalisable according to Symbolab. 

Questions : 
Is this method applicable to other recurrence than just Fibonacci sequence ? Is there a special name to these recurrence relations ?
 A: Yes, ultimately, the reason why we end up with diagonalization is because we ended up exponentiation of a matrix $A$, that is we want to compute $A^n$ efficiently. 
Suppose the matrix $A$ is diagonalizable, then it can be written as $A=PDP^{-1}$ and $A^n = PD^nP^{-1}$.
Suppose it is not diagonalizable, we still have other decomposition, for instance, we have Jordan canonical form, $A=PJP^{-1}$ and $A^n=PJ^nP^{-1}$.
Formula for exponent of Jordan canonical form can be found here.
A: Building on Siong's answer, with Jordan normal form we can efficiently exponentiate $A$, but the $A$ in your question with respect to the second example is not quite correct. You should instead be looking for a matrix $A$ such that
$$
\begin{bmatrix} F(n + 2) \\ F(n + 1) \\ 1 \end{bmatrix} = A \begin{bmatrix} F(n + 1) \\ F(n) \\ 1 \end{bmatrix} = A^n \begin{bmatrix} 2 \\ 4 \\ 1 \end{bmatrix}.
$$
In this case, we have $A = \begin{bmatrix} 4 & -3 & 16 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}, J = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 3 \end{bmatrix}, P = \begin{bmatrix} 1 & 0 & 1 \\ 1 & 0 & \frac{1}{3} \\ 0 & -\frac{1}{8} & 0 \end{bmatrix}$.
