Year: 2014
Paper: 3
Question Number: 8
Course: UFM Pure
Section: Sequences and series, recurrence and convergence
A 10% increase in the number of candidates and the popularity of all questions ensured that all questions had a good number of attempts, though the first two questions were very much the most popular. Every question received at least one absolutely correct solution. In most cases when candidates submitted more than six solutions, the extra ones were rarely substantial attempts. Five sixths gave in at least six attempts.
Difficulty Rating: 1700.0
Difficulty Comparisons: 0
Banger Rating: 1516.0
Banger Comparisons: 1
The numbers $f(r)$ satisfy $f(r)>f(r+1)$ for $r=1, 2,
\dots$. Show that, for any non-negative integer $n$,
\[
k^n(k-1) \, f(k^{n+1}) \le \sum_{r=k^n}^{k^{n+1}-1}f(r) \le k^n(k-1)\,
f(k^n)\,
\]
where $k$ is an integer greater than 1.
\begin{questionparts}
\item By taking $f(r) = 1/r$, show that
\[
\frac{N+1}2 \le \sum_{r=1}^{2^{N+1}-1} \frac1r \le N+1 \,.
\]
Deduce that the sum $\displaystyle \sum_{r=1}^\infty \frac1r$ does not converge.
\item By taking $f(r)= 1/r^3$, show that
\[
\sum_{r=1}^\infty \frac1 {r^3} \le 1 \tfrac 13 \,.
\]
\item Let $S(n)$ be the set of positive integers less than $n$ which do not have a $2$ in their decimal representation and let $\sigma(n)$ be the sum of the reciprocals of the numbers in $S(n)$, so for example $\sigma(5) = 1+\frac13+\frac14$. Show that $S(1000)$ contains $9^3-1$ distinct numbers.
Show that $\sigma (n) < 80$ for all $n$.
\end{questionparts}\begin{align*}
&& \sum_{r=k^n}^{k^{n+1}-1} f(r) &\leq \sum_{r=k^n}^{k^{n+1}-1} f(k^{n}) \\
&&&= (k^{n+1}-k^n)f(k^n) \\
&&&= k^n(k-1)f(k^n) \\
\\
&& \sum_{r=k^n}^{k^{n+1}-1} f(r) &\geq \sum_{r=k^n}^{k^{n+1}-1} f(k^{n+1}) \\
&&&= (k^{n+1}-k^n)f(k^{n+1}) \\
&&&= k^n(k-1)f(k^{n+1}) \\
\end{align*}
\begin{questionparts}
\item Notice that if $f(r) = 1/r$ then $f(r) > f(r+1)$ so we can apply our lemma, ie
\begin{align*}
&&&2^N(2-1) \frac{1}{2^{N+1}} &\leq & \sum_{r=2^N}^{2^{N+1}-1} \frac1r &\leq&\quad 2^N(2-1) \frac{1}{2^{N}} \\
\Leftrightarrow &&& \frac12 &\leq &
\sum_{r=2^N}^{2^{N+1}-1} \frac1r &\leq&\quad 1 \\
\Rightarrow &&& \frac12+\frac12+\cdots+\frac12 &\leq &
\underbrace{\sum_{r=2^0}^{2^{0+1}-1} \frac1r+\sum_{r=2^1}^{2^{1+1}-1} \frac1r+\cdots+\sum_{r=2^N}^{2^{N+1}-1} \frac1r}_{N+1 \text{ terms}} &\leq&\quad 1 +1+\cdots+1\\
\Rightarrow &&& \frac{N+1}{2} &\leq &
\underbrace{\sum_{r=1}^{2^{N+1}-1} \frac1r}_{N+1 \text{ terms}} &\leq&\quad N+1
\end{align*}
Therefore the sum $\displaystyle \sum_{r=1}^{2^{N+1}-1} \frac1r$ is always greater than $N+1$ and in particular we can find an upper limit such that it is always bigger than any value, ie it diverges.
\item If $f(r) = 1/r^3$ then we have
\begin{align*}
&& \sum_{r=2^N}^{2^{N+1}-1} \frac1{r^3} &\leq 2^N(2-1) \frac{1}{2^{3N}} \\
&&&= \frac{1}{4^N} \\
\Rightarrow && \sum_{r=2^0}^{2^{0+1}-1} \frac1{r^3} +\sum_{r=2^1}^{2^{1+1}-1} \frac1{r^3} +\sum_{r=2^N}^{2^{N+1}-1} \frac1{r^3} &\leq 1 + \frac14 + \cdots + \frac1{4^N} \\
\Rightarrow && \sum_{r=1}^{\infty} \frac1{r^3} &\leq 1 + \frac14 + \cdots \\
&&&= \frac{1}{1-\frac14} = \frac43 = 1\tfrac13
\end{align*}
\item To count the number of numbers less than $1000$ without a $2$ in their decimal representation we can count the number of $3$ digit numbers (where $0$ is an acceptable leading digit) which don't contain a $2$ and remove $0$. There are $9$ choices for each digit, so $9^3-1$. Notice this is true for $10^N$ for any $N$, ie $S(10^N) = 9^N-1$.
Notice also that we can now write:
\begin{align*}
&& \sum_{r=10^N }^{10^{N+1}-1} \frac{1}{r} \mathbb{1}_{r \in S} & < \frac{1}{10^{N+1}}\#\{\text{number not containing a }2\} \\
&&&= \frac{1}{10^{N+1}}((9^{N+1}-1)-(9^N-1)) \\
&&&= \frac{9^N}{10^N}(9-1) \\
&&&= 8 \cdot \left (\frac9{10} \right)^N \\
\\
\Rightarrow && \sum_{r=1}^{\infty} \frac{1}{r} \mathbb{1}_{r \in S} &< 8\left ( 1 + \frac9{10} + \cdots \right) \\
&&&= 8 \frac{1}{1-\frac{9}{10}} = 80
\end{align*}
\end{questionparts}
Just fewer than half the candidates attempted this scoring just over a third of the marks. Many managed all but part (iii) easily but few managed that last part, and most did not try it. In part (i), having correctly used the result from the stem, there was frequently not enough care taken in extending this to the full sum. A not infrequent error of logic was that ∑(1/(n+1)) > 1 and lim n→∞ 1/n = ∞ somehow implies that ∑1/n does not converge.