<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] With $\{e_1, e_2, e_3\}$ as your base, check what happens when you operate on them
$$Ae_1 = e_3 \implies A^ne_1 = A^{n-1}e_3$$
$$Ae_2 = e_2+e_3 \implies A^ne_2 = A^{n-1}(e_2+e_3) = A^{n-1}e_3 + A^{n-1}e_2$$
$$Ae_3 = e_1+e_2+e_3\implies A^ne_3 = A^{n-1}(e_1+e_2+e_3) = $$
$$ = A^{n-1}e_1+A^{n-1}e_2+A^{n-1}e_3 = 2A^{n-2}e_3+A^{n-2}e_2 +A^{n-1}e_3$$
This implies a recursive expression for each of your columns, maybe it can be tweaked a bit further.
</s>