Problems

Filters
Clear Filters

2 problems found

2014 Paper 3 Q8
D: 1700.0 B: 1516.0
sequences series convergence inequality harmonic series bounding sums decreasing function geometric grouping divergence decimal representation

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.

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

Solution: \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*}

  1. 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.
  2. 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*}
  3. 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*}

View
1994 Paper 2 Q1
D: 1600.0 B: 1484.0
proof number theory divisibility decimal representation modular arithmetic existence proof digit properties

In this question we consider only positive, non-zero integers written out in the usual (decimal) way. We say, for example, that 207 ends in 7 and that 5310 ends in 1 followed by 0. Show that, if \(n\) does not end in 5 or an even number, then there exists \(m\) such that \(n\times m\) ends in 1. Show that, given any \(n\), we can find \(m\) such that \(n\times m\) ends either in 1 or in 1 followed by one or more zeros. Show that, given any \(n\) which ends in 1 or in 1 followed by one or more zeros, we can find \(m\) such that \(n\times m\) contains all the digits \(0,1,2,\ldots,9\).

Solution: \begin{array}{c|c} \text{ends in} & \text{multiply by} \\ \hline 1 & 1 \\ 3 & 7 \\ 7 & 3 \\ 9 & 9 \end{array} If if \(n = 2^a \cdot 5^b \cdot c\) where \(c\) has no factors of \(2\) and \(5\) then we can multiply by \(2^b \cdot 5^a\) to obtain \(c\) followed by \(0\)s. Since \(c\) is neither even, nor a multiple of \(5\), by the earlier part of the question we can find a multiple such that it ends in \(1\). Suppose it is a \(k\) digit number, the consider Now consider \(1\underbrace{00\cdots0}_{k\text{ digits}}2\underbrace{00\cdots0}_{k\text{ digits}}\cdots 8\underbrace{00\cdots0}_{k\text{ digits}}9\cdot 0\), then clearly each section will end in the leading digit (ie all digits from \(1\) to \(9\)) and also end with a \(0\)

View