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})$ 
$\newcommand{\tr}{\operatorname{tr}}$ If $A =   \begin{bmatrix}
     0 & 1  \\
     1 & 1    \end{bmatrix} $, then $\tr(A^{k}) = \tr(A^{k-1}) + \tr(A^{k-2})$.
Hint: If $AB=0$, then $\tr[(A+B)^k]=\tr(A^k)+\tr(B^k)$.

I tried to decompose \begin{bmatrix}
    0 & 1  \\
    1 & 1 
  \end{bmatrix} to $P$ and $Q$ such that $P+Q=\begin{bmatrix}
    0 & 1  \\
    1 & 1 
  \end{bmatrix}$ and $PQ=0$, but it seems that this does not work.

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