Year: 2025
Paper: 2
Question Number: 4
Course: LFM Pure
Section: Proof by induction
As is commonly the case, the vast majority of candidates focused on the Pure questions in Section A of the paper, with a good number of attempts made on all of those questions. Candidates that attempted the Mechanics questions in Section B generally answered both questions. More candidates attempted Question 11 in Section C than either Mechanics question, but very few attempted Question 12 in that section. There were a large number of good responses seen for all the questions, but a significant number of responses lacked sufficient detail in the presentation, particularly when asked to prove a given result or provide an explanation. Candidates who did well on this paper generally: gave careful explanations of each step within their solutions; indicated all points of interest on graphs and other diagrams clearly; made clear comments about the approach that needed to be taken, particularly when having to explore a number of cases as part of the solution to a question; used mathematical terminology accurately within their solutions. Candidates who did less well on this paper generally: made errors with basic algebraic manipulation, such as incorrect processing of indices; produced sketches of graphs in which significant points were difficult to see clearly because of the chosen scale; skipped important lines within lengthy sections of algebraic reasoning.
Difficulty Rating: 1500.0
Difficulty Comparisons: 0
Banger Rating: 1500.0
Banger Comparisons: 0
Let $\lfloor x \rfloor$ denote the largest integer that satisfies $\lfloor x \rfloor \leq x$.
For example, if $x = -4.2$, then $\lfloor x \rfloor = -5$.
\begin{questionparts}
\item Show that, if $n$ is an integer, then $\lfloor x + n \rfloor = \lfloor x \rfloor + n$.
\item Let $n$ be a positive integer and define function $f_n$ by
\[f_n(x) = \lfloor x \rfloor + \left\lfloor x + \frac{1}{n} \right\rfloor + \left\lfloor x + \frac{2}{n} \right\rfloor + \ldots + \left\lfloor x + \frac{n-1}{n} \right\rfloor - \lfloor nx \rfloor\]
\begin{enumerate}
\item Show that $f_n\left(x + \frac{1}{n}\right) = f_n(x)$.
\item Evaluate $f_n(t)$ for $0 \leq t < \frac{1}{n}$.
\item Hence show that $f_n(x) \equiv 0$.
\end{enumerate}
\item
\begin{enumerate}
\item Show that $\left\lfloor \frac{x}{2} \right\rfloor + \left\lfloor \frac{x+1}{2} \right\rfloor = \lfloor x \rfloor$.
\item Hence, or otherwise, simplify
\[\left\lfloor \frac{x+1}{2} \right\rfloor + \left\lfloor \frac{x+2}{2^2} \right\rfloor + \ldots + \left\lfloor \frac{x+2^k}{2^{k+1}} \right\rfloor + \ldots\]
\end{enumerate}
\end{questionparts}\begin{questionparts}
\item Claim: If $n \in \mathbb{Z}$ then $\lfloor x + n \rfloor = \lfloor x \rfloor + n$
Proof: Since $\lfloor x \rfloor \leq x$ then $\lfloor x \rfloor + n \leq x + n$ and $\lfloor x \rfloor + n \in \mathbb{Z}$ we must have that $\lfloor x \rfloor +n \leq \lfloor x + n \rfloor$. However, since $\lfloor x \rfloor + 1 > x$ we must also have that $\lfloor x \rfloor + 1 + n > x + n$, therefore $\lfloor x \rfloor + n$ is the largest integer less than $x + n$ as required.
\item \begin{enumerate}
\item Claim: $f_n\left(x + \frac{1}{n}\right) = f_n(x)$
Proof:
\begin{align*}
f_n\left(x + \frac{1}{n}\right) &=\left \lfloor x+ \frac{1}{n} \right \rfloor + \left\lfloor x + \frac{1}{n}+ \frac{1}{n} \right\rfloor + \left\lfloor x+ \frac{1}{n} + \frac{2}{n} \right\rfloor + \ldots + \left\lfloor x+ \frac{1}{n} + \frac{n-1}{n} \right\rfloor - \left \lfloor n\left ( x + \frac{1}{n} \right) \right \rfloor \\
&= \left \lfloor x+ \frac{1}{n} \right \rfloor + \left\lfloor x + \frac{2}{n}\right\rfloor + \left\lfloor x+ \frac{3}{n} \right\rfloor + \ldots + \left\lfloor x+ \frac{n}{n} \right\rfloor - \left \lfloor nx + 1 \right \rfloor \\
&= \left \lfloor x+ \frac{1}{n} \right \rfloor + \left\lfloor x + \frac{2}{n}\right\rfloor + \left\lfloor x+ \frac{3}{n} \right\rfloor + \ldots + \left\lfloor x+ 1 \right\rfloor - \left \lfloor nx + 1 \right \rfloor \\
&= \left \lfloor x+ \frac{1}{n} \right \rfloor + \left\lfloor x + \frac{2}{n}\right\rfloor + \left\lfloor x+ \frac{3}{n} \right\rfloor + \ldots + \lfloor x \rfloor + 1 - \left ( \lfloor nx \rfloor + 1 \right) \\
&= \lfloor x \rfloor + \left\lfloor x + \frac{1}{n} \right\rfloor + \left\lfloor x + \frac{2}{n} \right\rfloor + \ldots + \left\lfloor x + \frac{n-1}{n} \right\rfloor - \lfloor nx \rfloor \\
&= f_n(x)
\end{align*}
\item Suppose $0 \leq t < \frac1n$, then note that $\left \lfloor t + \frac{k}{n} \right \rfloor = 0$ for $0 \leq k \leq n - 1$ and $\lfloor n t \rfloor = 0$ since $nt < 1$
\item Since $f_n(x)$ is zero on $[0, \tfrac1n)$ and periodic with period $\tfrac1n$ it must be constantly zero
\end{enumerate}
\item \begin{enumerate}
\item Claim: $\left\lfloor \frac{x}{2} \right\rfloor + \left\lfloor \frac{x+1}{2} \right\rfloor = \lfloor x \rfloor$
Proof: Suppose $x = n + \epsilon$ where $0 \leq \epsilon < 1$, ie $n = \lfloor x \rfloor$, then consider two cases:
Case 1: $n = 2k$
\begin{align*}
\left\lfloor \frac{x}{2} \right\rfloor + \left\lfloor \frac{x+1}{2} \right\rfloor &= \left\lfloor \frac{n + \epsilon}{2} \right\rfloor + \left\lfloor \frac{n + \epsilon+1}{2} \right\rfloor \\
&= \left\lfloor \frac{2k + \epsilon}{2} \right\rfloor + \left\lfloor \frac{2k + \epsilon+1}{2} \right\rfloor \\
&= k + \left\lfloor \frac{\epsilon}{2} \right\rfloor + k + \left\lfloor \frac{\epsilon+1}{2} \right\rfloor \\
&= 2k \\
&= n
\end{align*}
Case 2: $n = 2k + 1$
\begin{align*}
\left\lfloor \frac{x}{2} \right\rfloor + \left\lfloor \frac{x+1}{2} \right\rfloor &= \left\lfloor \frac{n + \epsilon}{2} \right\rfloor + \left\lfloor \frac{n + \epsilon+1}{2} \right\rfloor \\
&= \left\lfloor \frac{2k +1+ \epsilon}{2} \right\rfloor + \left\lfloor \frac{2k +1+ \epsilon+1}{2} \right\rfloor \\
&= k + \left\lfloor \frac{\epsilon+1}{2} \right\rfloor + k +1+ \left\lfloor \frac{\epsilon}{2} \right\rfloor \\
&= 2k +1\\
&= n
\end{align*}
as required.
\item Since $\left \lfloor \frac{x+1}{2} \right \rfloor = \lfloor x \rfloor - \lfloor \frac{x}{2} \rfloor$ and in general, $\left \lfloor \frac{x+2^k}{2^{k+1}} \right \rfloor = \lfloor \frac{x}{2^k} \rfloor - \lfloor \frac{x}{2^{k+1}} \rfloor$ and so in general:
\begin{align*}
\sum_{k=0}^\infty \left \lfloor \frac{x+2^k}{2^{k+1}} \right \rfloor &= \sum_{k=0}^\infty \left ( \left \lfloor \frac{x}{2^k} \right \rfloor -\left \lfloor \frac{x}{2^{k+1}} \right \rfloor \right) \\
&= \lfloor x \rfloor
\end{align*}
\end{enumerate}
\end{questionparts}
This was a popular question, but candidates often struggled to explain their reasoning with sufficient clarity in many parts. Almost all candidates seemed to understand why the result in part (i) is true, but many were not precise enough in their explanation. The most common approach was to split x as the sum of two values, one of which was an integer, but many candidates did not state that the other part of the number was greater than or equal to 0 and strictly less than 1. Part (ii) (a) was answered well in general, with almost all candidates realising that part (i) could be applied here. Solutions were often very well presented for this part. Part (ii) (b) also had many good responses, but in some cases the justification that one or more of the terms must be equal to 0 was missing. Many candidates realised that they could combine the results from the previous two parts to obtain this result, but many arguments were incomplete. In particular, some only showed that the result applied for x ≥ 0. Part (iii) (a) was answered well, with most candidates choosing to split the argument into two cases. A significant number realised that this is also a special case of the result in part (ii) (c) and obtained the result from the fact that f2(x/2) = 0. Many candidates realised in part (iii) (b) that the result from (iii) (a) could be applied so that the sum could be expressed in a form where most terms cancelled. A common mistake was simply to claim that all but the first term in the sum would cancel and ignore the final term of the partial sum. A few candidates successfully managed to find the complete solution by considering the cases for the different signs of x.