Find large power of a non-diagonalisable matrix

Notice the characteristic polynomial of $A$ is $$\chi_A(\lambda) \stackrel{def}{=}\det(\lambda I_3 - A) = \lambda^3-\lambda^2-\lambda+1 = (\lambda^2-1)(\lambda-1)$$ By Cayley-Hamilton theorem, we have

$$\chi_A(A) = (A^2 - I)(A-I) = 0 \quad\implies (A^2-I)^2 = (A^2-I)(A-I)(A+I) = 0$$

This means $A^2-I$ is nilpotent. In following binary expansion of $A^{30}$

$$A^{30} = (I + (A^2 - I))^{15} = \sum_{k=0}^{15} \binom{15}{k}(A^2-I)^k$$

only the term $k = 0$ and $1$ contributes. i.e.

$$A^{30} = I + 15 (A^2-I) = \begin{bmatrix} 1 & 0 & 0\\ 15 & 1 & 0\\ 15 & 0 & 1 \end{bmatrix} $$

You can use repeated squaring to efficiently compute large powers.

$$ A^{30} = A^{16} \cdot A^8 \cdot A^4 \cdot A^2$$

where $A^4 = {A^2} ^2$, $A^8= {A^4}^2$, etc.

Since the given matrix is rather simple, you could also compute a few powers:

\begin{align*} A^1&= \begin{pmatrix} 1 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}\\ A^2&= \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix}\\ A^3&= \begin{pmatrix} 1 & 0 & 0 \\ 2 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}\\ A^4&= \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 2 & 0 & 1 \end{pmatrix}\\ A^5&= \begin{pmatrix} 1 & 0 & 0 \\ 3 & 0 & 1 \\ 2 & 1 & 0 \end{pmatrix}\\ A^6&= \begin{pmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 3 & 0 & 1 \end{pmatrix}\\ \end{align*}

Can you notice some kind of pattern and prove it by induction? (Or, if you prefer, you can do the same thing with $B=A^2$ and try to find general form of $B^n$.)

---

Of course, this is "naive" approach - without using any theory you have learned about matrices. For more complicated matrices it would be rather difficult to spot some kind of pattern. That's why methods which work for arbitrary matrices are more useful.