Year: 2023
Paper: 2
Question Number: 6
Course: LFM Pure
Section: Proof by induction
No solution available for this problem.
Many candidates were able to express their reasoning clearly and presented good solutions to the questions that they attempted. There were excellent solutions seen for all of the questions. An area where candidates struggled in several questions was in the direction of the logic that was required in a solution. Some candidates failed to appreciate that separate arguments may be needed for the "if" and "only if" parts of a question and, in some cases, candidates produced correct arguments, but for the wrong direction. In several questions it was clear that candidates who used sketches or diagrams generally performed much better that those who did not. Sketches often also helped to make the solution clearer and easier to understand. Several questions on the STEP papers ask candidates to show a given result. Candidates should be aware that there is a need to present sufficient detail in their solutions so that it is clear that the reasoning is well understood.
Difficulty Rating: 1500.0
Difficulty Comparisons: 0
Banger Rating: 1500.0
Banger Comparisons: 0
The sequence $F_n$, for $n = 0, 1, 2, \ldots$, is defined by $F_0 = 0$, $F_1 = 1$ and by $F_{n+2} = F_{n+1} + F_n$ for $n \geqslant 0$.
Prove by induction that, for all positive integers $n$,
\[\begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix} = \mathbf{Q}^n,\]
where the matrix $\mathbf{Q}$ is given by
\[\mathbf{Q} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}.\]
\begin{questionparts}
\item By considering the matrix $\mathbf{Q}^n$, show that $F_{n+1}F_{n-1} - F_n^2 = (-1)^n$ for all positive integers $n$.
\item By considering the matrix $\mathbf{Q}^{m+n}$, show that $F_{m+n} = F_{m+1}F_n + F_m F_{n-1}$ for all positive integers $m$ and $n$.
\item Show that $\mathbf{Q}^2 = \mathbf{I} + \mathbf{Q}$.
In the following parts, you may use without proof the Binomial Theorem for matrices:
\[(\mathbf{I} + \mathbf{A})^n = \sum_{k=0}^{n} \binom{n}{k} \mathbf{A}^k.\]
\begin{enumerate}
\item[(a)] Show that, for all positive integers $n$,
\[F_{2n} = \sum_{k=0}^{n} \binom{n}{k} F_k\,.\]
\item[(b)] Show that, for all positive integers $n$,
\[F_{3n} = \sum_{k=0}^{n} \binom{n}{k} 2^k F_k\]
and also that
\[F_{3n} = \sum_{k=0}^{n} \binom{n}{k} F_{n+k}\,.\]
\item[(c)] Show that, for all positive integers $n$,
\[\sum_{k=0}^{n} (-1)^{n+k} \binom{n}{k} F_{n+k} = 0\,.\]
\end{enumerate}
\end{questionparts}
Most candidates were able to complete the proof by induction on which the other parts of the question are based. In some cases, the matrix multiplication was not completed correctly (such as calculating the product AB rather than BA). Throughout the question some candidates also got confused about the different variables involved although in some cases where this was clearly simply a mislabelling, they were given the benefit of the doubt. Most candidates were able to see how the relevant matrices could be used to obtain answers for both part (i) and part (ii), but in a small number of cases there was insufficient justification to show that the way in which the result was deduced had been understood. In part (iii) most candidates were able to show that Q² = I + Q, but many candidates were unable to make much more progress from this point. There were a small number of excellent solutions, carefully checking all of the relevant cases in each part and providing very clear explanations of the reasoning.