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.
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.
By taking \(f(r)= 1/r^3\), show that
\[
\sum_{r=1}^\infty \frac1 {r^3} \le 1 \tfrac 13 \,.
\]
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\).
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.
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*}