Find the power of the matrix. Let $A = \left( {\begin{array}{*{20}{c}}
0&1&1\\
1&0&1\\
1&1&0
\end{array}} \right)$.
I want to find $A^k,$ where $k \in N$. So far I calculated $A^2, A^3, A^4,...$ but I can not see the general formula for $A^k$. Here are $A^2, A^3, A^4, A^5$.

Not sure if this leads to anything but I found the general formula for $B^k$, where $B = \left( {\begin{array}{*{20}{c}}
1&1&1\\
1&1&1\\
1&1&1
\end{array}} \right)$.
${B^k} = \left( {\begin{array}{*{20}{c}}
{{3^{k - 1}}}&{{3^{k - 1}}}&{{3^{k - 1}}}\\
{{3^{k - 1}}}&{{3^{k - 1}}}&{{3^{k - 1}}}\\
{{3^{k - 1}}}&{{3^{k - 1}}}&{{3^{k - 1}}}
\end{array}} \right)$
Thanks in advance.
 A: Note that you get $$A^2=A+2I$$
Therefore $A^n$ is a linear combination of $A$ and $I\ $, i.e. $$ A^n=a_nA+i_nI$$
You get $A^{n+1}=a_nA^2+i_nA=a_n(A+2I)+i_nA=(a_n+i_n)A+2a_nI$
The system to solve is $\begin{cases}a_{n+1}=a_n+i_n\\i_{n+1}=2a_n\end{cases}\ $ and reporting for $a_{n+2}$ gives $\begin{cases}a_{n+2}=a_{n+1}+2a_n\\ a_0=0\\ a_1=1\end{cases}$
This solves to $a_n=\alpha\,2^n+\beta\,(-1)^n$ and initial conditions give $\ \alpha=-\beta=\frac 13$
A: Given matrix is real symmetric and hence diagonalisable. Hence $A=PDP^{-1}$. Thus $A^n$=$PD^nP^{-1}$ where P is the matrix of eigen vectors. D is diagonal and hence its powers are simply the powers of the eigenvalues which are $2,-1,-1$.
A: Hint. From the first few examples you gave, it is easy to conjecture that $A^n = a_nB+(-1)^nI$ for some sequence $(a_n)$ that starts off $1,1,3,5,11,\dots$. If this is the case, then we would have $$a_{n+1}B+(-1)^{n+1}I=A(a_nB+(-1)^nI)=a_nAB+(-1)^nA$$ for all $n$. Rearranging, and substituting the relationship $A+I=B$, this is equivalent to $$(a_{n+1}+a_n+(-1)^{n+1})B=a_nB^2.$$Now it is easy to see that $a_{n+1}+a_n+(-1)^{n+1}=3a_n$, so we have a recurrence for $(a_n)$ which can be solved by standard methods.
