With a given matrix $A \in M_3(\mathbb{R})$ show that $A^{2009} + A^{2008} = 2 ^{2008} (A + I_3)$. I am given the matrix:
$$A = \begin{pmatrix}
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 0 \\
\end{pmatrix}$$
I have to show that the following is true:
$$A ^ {2009} + A ^ {2008} = 2 ^ {2008} (A + I_3)$$
I calcucalted $A^2, A^3, A^4,...$ in hopes that I would find some kind of pattern, but I didn't.

More generally, $A^{n+1} + A^{n} = 2 ^{n} (A + I)$ for all $n \in \mathbb N$. This is proved by induction using that the minimal polynomial of $A$ is $x^2-  x - 2=(x-2)(x+1)$ and so $A^2=A+2I$:
$$
A^{n+2} + A^{n+1} = A(A^{n+1} + A^{n})= A(2^{n} (A + I))=2^n(A^2+A)= 2^n(2A+2I)=2^{n+1} (A + I)
$$
(The characteristic polynomial of $A$ is $x^3-3x-2=(x - 2) (x + 1)^2$. So the minimal polynomial of $A$ is either $(x - 2) (x + 1)^2$ or $(x - 2) (x + 1)$.)
