- Show that \[x^4=x+2x^2\qquad\text{and}\qquad x^5=2+4x+x^2.\]

If we multiply \(\eqref{eq:star}\) by \(x\), we obtain the first of the two equations.

For the second one, we multiply \(\eqref{eq:star}\) by \(x^2\) to get \(x^5=2x^3+x^2\). We can now substitute \(x^3\) using \(\eqref{eq:star}\), and the equation becomes \[x^5=2(2x+1)+x^2=x^2+4x+2.\]

- For every integer \(k\geq0\), we can uniquely write \[x^k=A_k+B_kx+C_kx^2\] where \(A_k\), \(B_k\), \(C_k\) are integers. So, in part (i), it was shown that \[A_4=0,\ B_4=1,\ C_4=2 \qquad\text{and}\qquad A_5=2,\ B_5=4,\ C_5=1.\] Show that \[A_{k+1}=C_k,\qquad B_{k+1}=A_k+2C_k,\qquad C_{k+1}=B_k.\]

Since \(x^k=A_k+B_kx+C_kx^2\), we can multiply this by \(x\) to obtain \[x^{k+1}=A_kx+B_kx^2+C_kx^3.\] We can then use \(\eqref{eq:star}\) to rewrite \(x^3\) as \(2x+1\), and thereby obtain (after collecting like terms): \[x^{k+1}=C_k+(A_k+2C_k)x+B_kx^2.\] But we also have, from the statement of the question, that \[x^{k+1}=A_{k+1}+ B_{k+1}x+C_{k+1}x^2.\] Since the coefficients in the two ways of writing out \(x^{k+1}\) must be equal, we get \(A_{k+1}=C_k\), \(B_{k+1}=A_k+2C_k\) and \(C_{k+1}=B_k\) as required.

- Let \[D_k=A_k+C_k-B_k.\] Show that \(D_{k+1}=-D_k\) and hence that \[A_k+C_k=B_k+(-1)^k.\]

Using the results from the previous part and the fact that \(D_{k+1}=A_{k+1}+C_{k+1}-B_{k+1}\), we get \[D_{k+1}=C_k+B_k-(A_k+2C_k)=-(A_k+C_k-B_k)=-D_k.\]

Rearranging the equation \(D_k=A_k+C_k-B_k\), we get \(A_k+C_k=B_k+D_k\). Therefore we now need to show that \(D_k=(-1)^k\).

We will prove by induction that \(D_k=(-1)^k\), for every \(k\geq3\).

For \(k=3\), \(A_3=1\), \(B_3=2\), \(C_3=0\), so \(D_3=1+0-2=-1=(-1)^3\), so the result holds.

If the result holds for \(k\), then, as \(D_{k+1}=-D_k\), \[D_{k+1}=-(-1)^k=(-1)^{k+1}.\]

So, by mathematical induction, \(D_k=(-1)^k\), and therefore \(A_k+C_k=B_k+(-1)^k\), as required.

- Let \(F_k=A_{k+1}+C_{k+1}\). Show that \[F_k+F_{k+1}=F_{k+2}.\]

We will rewrite \(F_{k+1}\) and \(F_{k+2}\) in terms of \(A_{k+1}\), \(B_{k+1}\) and \(C_{k+1}\), using the results of part (ii) repeatedly.

\[\begin{align} &F_{k+1}=A_{k+2}+C_{k+2}=C_{k+1}+B_{k+1} \label{eq:1}\\ &F_{k+2}=A_{k+3}+C_{k+3}=C_{k+2}+B_{k+2}= B_{k+1}+A_{k+1}+2C_{k+1}\label{eq:2} \end{align}\]By \(\eqref{eq:1}\), \[F_k+F_{k+1}=A_{k+1}+C_{k+1}+C_{k+1}+B_{k+1}= A_{k+1}+B_{k+1}+2C_{k+1},\] so, by equation \(\eqref{eq:2}\), \[F_k+F_{k+1}=F_{k+2}.\]