# Recurrence relation for a matrix

Question: If $A=\left[\begin{array}{ccc} 1 & 0 & 0\\ 1 & 0 & 1\\ 0 & 1 & 0\end{array}\right]$ then show that $A^n=A^{n-2}+A^2-I$, $n\geq3$. Hence find $A^{50}$.

Where do I begin? I solved upto $A^8=4A^2-I$ and $A^9=4A^2+A-I$ with similar pattern emerging but I'm stuck where to go from here. And since I'm starting from the equation I was supposed to arrive at, I don't think this is the solution. But I don't see anything I can do with $A$ to prove that equation except maybe calculate $A^2$...

-
To show the recurrence relation you can use induction. – user38268 Feb 15 '12 at 10:56
You refer to a "similar pattern emerging" but you need to see what that pattern actually is. Check what the even powers $A^{2n}$ are for $n=2,3,4,\dots$ in terms of $A^2$ and $I$. Can you conjecture a general formula? If you figure it out correctly, proving it with induction should be easy: use the formula on the power $A^{2n+2}$ and substitute in for $A^{2n}$ (we assume the hypothesis holds for evens up to $2n$). – anon Feb 15 '12 at 11:04

$1.~$ show for $n=3$ that :

$$A^3 =A^1+A^2-I \Rightarrow A(A^2-I)=A^2-I$$

$2.~$ suppose that :

$$A^n=A^{n-2}+A^2-I$$

EDIT :

As Brian correctly observed step $3$ should be :

$3.~$

\begin{align*} &A^{n+1}=A(A^{n-2}+A^2-I)=A^{n-1}+A(A^2-I)=A^{n-1}+A^2-I \end{align*}

which is true according to first induction step , so :

$$A^n=A^{n-2}+A^2-I\text{ for all }n \geq 3$$

Therefore :

\begin{align*} A^4&=2A^2-I\\ A^6&=3A^2-2I\\ A^8&=4A^2-3I\\ &\;\vdots\\ A^{50}&=25A^2-24I \end{align*}

-
The argument in step (3) is invalid as stated: showing that $P$ implies a true statement does not show that $P$ is true. You need to argue that if $A^n=A^{n-2}+A^2-I$, then $A^{n+1}=A(A^{n-2}+A^2-I)=A^{n-1}+A(A^2-I)=A^{n-1}+A^2-I$ by step (1). – Brian M. Scott Feb 15 '12 at 12:01