<s>[INST] 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.
 [/INST] 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.
</s>