<s>[INST] $A^{n}$ matrix problem without using $A=PDP^{-1}$ Eigendecomposition i have the following problem
Find $A^n$ for the following matrix
\begin{equation}
A=\begin{pmatrix}
0 & 0 & 1\\
0 & 1 & 1 \\
1 & 1 & 1
\end{pmatrix}
\end{equation}
I have tried the following, calculating for $n=1,2,3,4,5,6$
\begin{equation}
A^1=\begin{pmatrix}
0 & 0 & 1\\
0 & 1 & 1 \\
1 & 1 & 1
\end{pmatrix} \qquad \qquad 
A^2=\begin{pmatrix}
1 & 1 & 1\\
1 & 2 & 2 \\
1 & 2 & 3
\end{pmatrix} \qquad \qquad 
A^3=\begin{pmatrix}
1 & 2 & 3\\
2 & 4 & 5 \\
3 & 5 & 6 
\end{pmatrix} \\
A^4=\begin{pmatrix}
3 & 5 & 6\\
5 & 9 & 11 \\
6 & 11 & 14 
\end{pmatrix} \qquad \qquad 
A^5=\begin{pmatrix}
6 & 11 & 14\\
11 & 20 & 25 \\
14 & 25 & 31 
\end{pmatrix} \qquad \qquad 
A^6=\begin{pmatrix}
14 & 25 & 31\\
25 & 45 & 56 \\
31 & 56 & 70
\end{pmatrix}
\end{equation}
That gives the following terms
\begin{equation}
A_{11} = 0,1,1,3,6,14,...\\
A_{12} = 0,1,2,5,11,25,...\\
A_{22} = 1,2,4,9,20,45,...
\end{equation}
But i can't figure out the succesion in terms of n.
 [/INST] The following solution is using the eigenvalues in an implicit way.
$$A^3=2A^2+A-I_3$$
Which can be found by inspection or by calculating the characteristic polynomial.
Then, by long division
$$X^n=Q(X)(X^3-2X^2-X+1)+aX^2+bX+c$$
You can find $a,b,c$ by setting $X=\lambda_{1,2,3}$ the solutions to $X^3-2X^2-X+1$ in the above equation.
Then, setting $x=A$ in the equation we get:
$$A^n=aA^2+bA+C$$
Note The above implies that all entries of $A^n$ are of the form $c_1\lambda_1^n+c_2 \lambda_2^n+c_3 \lambda_3^n$ (which is consistent with diagonalisation). Since the roots
$\lambda_{1,2,3}$ of the equation
$$x^3-2x^2-x+1$$
are ugly, the formula is almost impossible to guess.
</s>