Year: 2017
Paper: 2
Question Number: 6
Course: LFM Pure
Section: Proof by induction
This year's paper was, perhaps, slightly more straightforward than usual, with more helpful guidance offered in some of the questions. Thus the mark required for a "1", a Distinction, was 80 (out of 120), around ten marks higher than that which would customarily be required to be awarded this grade. Nonetheless, a three‐figure mark is still a considerable achievement and, of the 1330 candidates sitting the paper, there were 89 who achieved this. At the other end of the scale, there were over 350 who scored 40 or below, including almost 150 who failed to exceed a total score of 25. As a general strategy for success in a STEP examination, candidates should be looking to find four "good" questions to work at (which may be chosen freely by the candidates from a total of 13 questions overall). It is unfortunately the case that so many low‐scoring candidates flit from one question to another, barely starting each one before moving on. There needs to be a willingness to persevere with a question until a measure of understanding as to the nature of the question's purpose and direction begins to emerge. Many low‐scoring candidates fail to deal with those parts of questions which cover routine mathematical processes ‐ processes that should be standard for an A‐level candidate. The significance of the "rule of four" is that four high‐scoring questions (15‐20 marks apiece) obtains you up to around the total of 70 that is usually required for a "1"; and with a couple of supporting starts to questions, such a total should not be beyond a good candidate who has prepared adequately. This year, significantly more than 10% of candidates failed to score at least half marks on any one question; and, given that Q1 (and often Q2 also) is (are) specifically set to give all candidates the opportunity to secure some marks, this indicates that these candidates are giving up too easily. Mathematics is about more than just getting to correct answers. It is about communicating clearly and precisely. Particularly with "show that" questions, candidates need to distinguish themselves from those who are just tracking back from given results. They should also be aware that convincing themselves is not sufficient, and if they are using a result from 3 pages earlier, they should make this clear in their working. A few specifics: In answers to mechanics questions, clarity of diagrams would have helped many students. If new variables or functions are introduced, it is important that students clearly define them. One area which is very important in STEP but which was very poorly done is dealing with inequalities. Although a wide range of approaches such as perturbation theory were attempted, at STEP level having a good understanding of the basics – such as changing the inequality if multiplying by a negative number – is more than enough. In fact, candidates who used more advanced methods rarely succeeded.
Difficulty Rating: 1600.0
Difficulty Comparisons: 0
Banger Rating: 1484.8
Banger Comparisons: 1
Let
\[
S_n = \sum_{r=1}^n \frac 1 {\sqrt r \ }
\,,
\]
where $n$ is a positive integer.
\begin{questionparts}
\item
Prove by induction that
\[
S_n \le 2\sqrt n -1\,
.
\]
\item
Show that $(4k+1)\sqrt{k+1} > (4k+3)\sqrt k\,$ for $k\ge0\,$.
Determine the smallest number $C$ such that
\[
S_n \ge 2\sqrt n + \frac 1 {2\sqrt n} -C
\,.\]
\end{questionparts}\begin{questionparts}
\item Claim: $S_n \leq 2\sqrt{n} -1$.
Proof: (By induction)
(Base case: $n = 1$). $\frac{1}{\sqrt{1}} \leq 1 = 2 \cdot \sqrt1 - 1$. Therefore the base case is true.
(Inductive step): Suppose our result is true for $n = k$. Then consider $n = k+1$.
\begin{align*}
&& \sum_{r=1}^{k+1} \frac{1}{\sqrt{r}} &=\sum_{r=1}^{k} \frac{1}{\sqrt{r}} + \frac{1}{\sqrt{k+1}} \\
&&&\leq 2\sqrt{k} - 1 + \frac{1}{\sqrt{k+1}} \\
&&&= \frac{2 \sqrt{k}\sqrt{k+1}+1}{\sqrt{k+1}} - 1 \\
&&&\underbrace{\leq}_{AM-GM} \frac{(k+k+1)+1}{\sqrt{k+1}} - 1 \\
&&&=\frac{2(k+1)}{\sqrt{k+1}} - 1 \\
&&&= 2\sqrt{k+1}-1
\end{align*}
Therefore, since if our statement is true for $n = k$, it is also true for $n = k+1$. By the principle of mathematical induction we can say that it is true for all $n \geq 1, n \in \mathbb{Z}$
\item Claim: $(4k+1)\sqrt{k+1} > (4k+3)\sqrt k\,$ for $k\ge0\,$
Proof: \begin{align*}
&& (4k+1)\sqrt{k+1} &> (4k+3)\sqrt k \\
\Leftrightarrow && (4k+1)^2(k+1) &> (4k+3)^2k \\
\Leftrightarrow && (16k^2+8k+1)(k+1) &> (16k^2 + 24k+9)k \\
\Leftrightarrow && 16 k^3 + 24 k^2 + 9 k +1&> 16k^3 + 24k^2+9k
\end{align*}
But this last inequality is clearly true, hence our original inequality is true.
Suppose $S_n \geq 2\sqrt{n} + \frac{1}{2 \sqrt{n}} - C$, then adding $\frac{1}{\sqrt{n+1}}$ to both sides we have:
\begin{align*}
S_{n+1} &\geq 2\sqrt{n} + \frac{1}{2 \sqrt{n}} - C + \frac{1}{\sqrt{n+1}} \\
&= 2\sqrt{n+1} + \frac{1}{2\sqrt{n+1}} - C + \frac{1}{2\sqrt{n+1}} +\frac{1}{2 \sqrt{n}} +2(\sqrt{n} - \sqrt{n+1})\\
&= 2\sqrt{n+1} + \frac{1}{2\sqrt{n+1}} - C + \frac{1}{2\sqrt{n+1}} +\frac{1}{2 \sqrt{n}} -\frac{2}{\sqrt{n+1} + \sqrt{n}}\\
\end{align*}
Therefore as long as the inequality is satisfied for $n=1$, ie $1 \geq 2\sqrt{1} + \frac{1}{2 \sqrt{1}} - C = \frac52 - C \Rightarrow C \geq \frac32$
\end{questionparts}
This question was relatively popular, but it turned out to be one of the hardest of the pure questions. The first part was a reasonably standard example of induction but nearly all candidates failed to understand the subtlety of what was required in the last part. Most candidates made significant progress with part (i), clearly being familiar with the process of induction. However, the algebra to complete the proof was too much for most candidates. Inequalities were frequently handled poorly and the general presentation of logical arguments was unclear with many candidates assuming what was required and not making implications clear. Attempts which brought in calculus were rarely relevant and even less frequently correct. In the second part, candidates tended to overcomplicate the question. Squaring up (since both sides are clearly positive) and expanding brackets was all that was required. It would have been nice if students had shown some awareness that the squaring process was valid since both sides were positive, however if we had required this it would have effectively been a one mark penalty for all candidates. In the final part candidates often considered to find a necessary bound on . However, further work – usually an induction using their guess – was required to show that this bound works for all . Many candidates seemed unaware that this final stage was required.