<s>[INST] Providing a closed formula for a linear recursive sequence I am studying for an exam in linear algebra and I have some trouble solving the following:
Let $(a_n)$ be a linear recursive sequence in $\mathbb{Z}_5$ with
\begin{align} 
a_0 = 2, a_1 = 1, a_2 = 0 \text{ and } a_{n+3} = 2a_{n+2} + a_{n+1} + 3a_n \text{ for }  n \in \mathbb{N}_0
\end{align}  
Provide a closed formula for $a_n$.
My findings so far:
$
\begin{pmatrix} a_{n+3}  \\ a_{n+2} \\ a_{n+1} \\ \end{pmatrix}
   = \begin{pmatrix} 2 & 1 & 3  \\1 & 0 & 0  \\ 0 & 1 & 0 \\ \end{pmatrix} \cdot \begin{pmatrix} a_{n+2}  \\ a_{n+1} \\ a_{n} \\ \end{pmatrix} 
$
$
\begin{pmatrix} a_{n}  \\ a_{n+1} \\ a_{n+2} \\ \end{pmatrix}
   = A^n \cdot \begin{pmatrix} a_{0}  \\ a_{1} \\ a_{2} \\ \end{pmatrix} = A^n \cdot \begin{pmatrix} 2  \\ 1 \\ 0 \\ \end{pmatrix} 
$
At some point there must hold the following:
\begin{align} 
T^{-1}AT = D = \begin{pmatrix} c_1 & 0 & 0  \\0 & c_2 & 0  \\ 0 & 0 & c_3 \\ \end{pmatrix}
\end{align} 
such that D is a diagonal matrix containing all Eigenwerte $c_i$, $i \in {\{1,2,3} \}$  of $A$.
How shall I continue to find the matrix $A$?
 [/INST] $$\begin{pmatrix}a_{n+3}\\a_{n+2}\\a_{n+1}\end{pmatrix}=\begin{pmatrix}2&1&3\\1&0&0\\0&1&0\end{pmatrix}\begin{pmatrix}a_{n+2}\\a_{n+1}\\a_n\end{pmatrix}=\ldots=\begin{pmatrix}2&1&3\\1&0&0\\0&1&0\end{pmatrix}^n\begin{pmatrix}2\\1\\0\end{pmatrix}$$
Now:
$$\det(tI-A)=\begin{vmatrix}t-2&-1&-3\\
-1&t&0\\
0&-1&t\end{vmatrix}=t^2(x-2)-3-t=(t^2-1)(t+3)\in\left(\Bbb Z/5\Bbb Z\right)[x]$$
Thus, the eigenvalues of the matrix are $\,-1,1,-3 = 1,2,4\pmod 5\;$:
$$\begin{align*}\lambda=1:& \implies \begin{cases}4x-y-3z=0\\{}\\4x+y=0\\{}\\4y+z=0\end{cases}\implies z=y=x\implies& \begin{pmatrix}1\\1\\1\end{pmatrix}\\{}\\
\lambda=2:&\implies\begin{cases}-y-3z=0\\{}\\-x+2y=0\\{}\\-y+2z=0\end{cases}\implies z\;,\;y=2z\;,\;x=4z\implies&\begin{pmatrix}4\\2\\1\end{pmatrix}\\{}\\
\lambda=4:&\implies\begin{cases}2x-y-3z=0\\{}\\-x+4y=0\\{}\\-y+4z=0\end{cases}\implies z\;,\;y=4z\;,\;x=3z\implies&\begin{pmatrix}3\\4\\1\end{pmatrix}\end{align*}$$
The above are corresponding eigenvectors to the corresponding eigenvalues, so now form the matrix:
$$P=\begin{pmatrix}1&4&3\\1&2&4\\1&1&1\end{pmatrix}$$
Find the matrix's inverse and then you'l get
$$P^{-1}AP=\begin{pmatrix}1&0&0\\
0&2&0\\0&0&4\end{pmatrix}=:D\implies P^{-1}A^nP=D^n $$
and this way you'll be able to solve your problem since exponentiating a diagonal matrix is a piece of cake... and don't forget to carry on arithmetic modulo $\,5\,$ all along!
</s>