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.
 A: 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.
A: I think your teacher has given a bad hint. It is far easier and more natural to solve the problem using the characteristic equation of $A$, as the comment  of  Jyrki Lahtonen or the other answer show. Anyway, we shall demystify your teacher's hint below. We suppose that the integer $k$ in question is nonnegative.
We first validate the statement in the hint. When $k\ge1$ and $XY=0$, the binomial expansion of $(X+Y)^k$ will be the sum of $X^k,\,Y^k$ and a number of interlaced products of $X$s and $Y$s. If an interlaced product contains $XY$ in its product sequence (such as $XXYXY$), the product as well as its trace are zero; if the product sequence doesn't contain $XY$, it must be of the form $Y^jX^{n-j}$ with $0<j<n$, and hence by the tracial property, $\operatorname{tr}(Y^jX^{n-j})=\operatorname{tr}(X^{n-j}Y^j)=0$. In other words, the trace of every interlaced product is zero. Thus we do have $\operatorname{tr}\left((X+Y)^k\right)=\operatorname{tr}(X^k)+\operatorname{tr}(Y^k)$.
Next, we want to decompose $A$ into $X+Y$ with $XY=0$. There are at least two ways to do this. The first way is to perform an eigendecomposition $A=V\operatorname{diag}(\lambda_1,\lambda_2)V^{-1}$ (this is possible because $A$ is real symmetric) and take $X=V\operatorname{diag}(\lambda_1,0)V^{-1},\,Y=V\operatorname{diag}(0,\lambda_2)V^{-1}$.
The second way is to solve $X(A-X)=0$. Note that if $X$ is invertible, we will get a useless solution $X=A$ and $Y=A-X=A$. So, we must assume that $X$ is singular but nonzero. Write $X=uv^T$. The equation $X(A-X)=0$ hence becomes $uv^T(A-uv^T)=0$, which can be rewritten as $uv^T(A-(v^Tu)I)=0$, meaning that $A$ is a left eigenpair $(\lambda,v)$ for some $\lambda$ and $u$ is a vector such that $v^Tu=\lambda$. It is not hard to see that we may pick $\lambda=\frac12(1+\sqrt{5})$ and $v=(1,\lambda)^T$. To make $v^Tu=\lambda$, we choose $u=(0,\frac1{\lambda})^T$. Thus
$$
A=X+Y=\pmatrix{0&0\\ 1&\lambda}+\pmatrix{0&1\\ 0&1-\lambda},\quad XY=0,
$$
and by your teacher's hint, $\operatorname{tr}(A^k)=\lambda^k+(1-\lambda)^k$ for every $k\ge1$. One can verify that this equality also holds for $k=0$. Thus the problem boils down to proving that
$$
\lambda^{k+2}+(1-\lambda)^{k+2}
=\left[\lambda^{k+1}+(1-\lambda)^{k+1}\right]
+\left[\lambda^k+(1-\lambda)^k\right]
$$
or that
$$
\left(\lambda^{k+2}-\lambda^{k+1}-\lambda^k\right)+
\left[(1-\lambda)^{k+2}-(1-\lambda)^{k+1}-(1-\lambda)^k\right]=0,
$$
but this is evident because both $\lambda$ and $1-\lambda$ are roots of $x^2-x-1=0$.
