Computing $A^{50}$ for a given matrix $A$

Let $e_1,e_2,e_3$ be the basis vectors. We have $Ae_2=e_3$ and $Ae_3=e_2$, so $A^{50}$ fixes both $e_2$ and $e_3$. We only need to check what $A^{50} e_1$ is. Calculate the first few: $$ Ae_1=e_1+e_2,~A^2e_1 =e_1+e_2+e_3, A^3e_1=e_1+2e_2+e_3. $$ We use induction to prove $A^{2k-1}e_1=e_1+k e_2 + (k-1)e_3$ and $A^{2k}e_1=e_1+ke_2+ke_3$. So $A^{50}e_1=e_1+25e_2+25e_3$ and $$ A^{50}=\begin{pmatrix}1&0&0\\25&1&0\\25&0&1\end{pmatrix} $$

the characteristic polynomial is \[ \chi_A(t) = (1-t)\bigl(t^2 - 1) \] so the eigenvalues are $\pm 1$, we have \[ A - 1 = \begin{pmatrix} 0 & 0 & 0\\\ 1 & -1 & 1 \\\ 0 & 1 & -1 \end{pmatrix} \] which has defect $1$ (so $A$ isn't diagonalizable). It holds \[ (A - 1)^2 = \begin{pmatrix} 0 & 0 & 0\\\ -1 & 2 & -2 \\\ 1 & -2 & 2 \end{pmatrix} \] so a basis of $\ker (A-1)^2$ is $\\{(2,1,0), (2,0,-1)\\}$, we have $A \cdot (2,1,0) = (0, 1, 1)$, so $\\{(2,1,0), (0,1,1)\\}$ is the basis of $\ker(A-1)^2$ we will use. It holds \[ A + 1 = \begin{pmatrix} 2 & 0 & 0\\\ 1 & 1 & 1 \\\ 0 & 1 & 1 \end{pmatrix} \] we choose the basis $\{(0,1,-1)\}$ of its kernel. So we let \[ S := \begin{pmatrix} 2 & 0 & 0\\\ 1 & 1 & 1 \\\ 0 & 1 & -1 \end{pmatrix} \] Then \[ S^{-1}AS = \begin{pmatrix} 1 & 0 & 0\\\ 1 & 1 & 0 \\\ 0 & 0 & -1 \end{pmatrix} \] so \[ S^{-1}A^{50}S = \begin{pmatrix} 1 & 0 & 0\\\ 50 & 1 & 0 \\\ 0 & 0 & -1 \end{pmatrix} \] and finally \[ A^{50} = \begin{pmatrix} 1 & 0 & 0\\\ 25 & 1 & 0 \\\ 25 & 0 & 1 \end{pmatrix} \]

The characteristic polynomial of $A$ is

$$X^3-X^2-X+1=(x-1)^2(x+1)$$

The Division Theorem tells us that

$$X^{50}=(X^3-X^2-X+1)Q(x)+ax^2+bx+c (*)$$

Plugging in $x=1$, $x=-1$ yield

$$1=a+b+c$$ $$1=a-b+c$$

Thus $b=0$ and $a+c=1$.

Differentiating $(*)$ and using the fact that $(X^3-X^2-X+1)Q(x)=(x-1)^2(something)$ we get

$$50x^{49}=(x-1)(junk)+2ax+b$$

Plugging in $a=1$ we get

$$50=2a+b$$

Thus $a=25, b=0, c=-24$

This proves that

$$X^{50}=(X^3-X^2-X+1)Q(x)+25x^2-24$$

Using the fact that $A^3-A^2-A+I =0$ we get

$$A^{50}=25A^2-24I$$

P.S. This is basically the same proof as Ihf 's, the only difference is that long division can replace the induction process.

To get the general formula, repeating the process for

$$X^{n}=(X^3-X^2-X+1)Q(x)+ax^2+bx+c (*)$$

yields

$$a+b+c=1$$ $$a-b+c =(-1)^n$$ $$2a+b=n$$

and

$$A^n= aA^2+bA+cI$$