Show that if $A = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} $, $\mathrm{tr}(A^{k}) = \mathrm{tr}(A^{k-1}) + \mathrm{tr}(A^{k-2})$
Solution 1:
Thank for the help! I think I figured it out. Here is my proof.
Proof: First note that $A^{2} = A + I_{2}$. Therefore, $A^{k} = A^{k-2} \cdot A^{2} = A^{k-2}(A + I_{2}) = A^{k-1} + A^{k-2}$. Therefore, $\operatorname{tr}(A^{k}) = \operatorname{tr}(A^{k-1} + A^{k-2}) = \operatorname{tr}(A^{k-1}) + \operatorname{tr}(A^{k-2})$, where the last equality follows from the fact that trace is a linear map.