Problems

Filters
Clear Filters

7 problems found

2015 Paper 2 Q1
D: 1600.0 B: 1516.0
Taylor series logarithm inequality summation harmonic series calculus monotonic function series bounds

  1. By use of calculus, show that \(x- \ln(1+x)\) is positive for all positive \(x\). Use this result to show that \[ \sum_{k=1}^n \frac 1 k > \ln (n+1) \,. \]
  2. By considering \( x+\ln (1-x)\), show that \[ \sum_{k=1}^\infty \frac 1 {k^2} <1+ \ln 2 \,. \]

Solution:

  1. Consider \(f(x) = x - \ln (1+ x)\), then \(f'(x) = 1 - \frac{1}{1+x} = \frac{x}{1+x} > 0\) if \(x >0\). Therefore \(f(x)\) is strictly increasing on the positive reals. Since \(f(0) = 0\) we must have \(f(x) > 0\) for all positive \(x\), ie \(x - \ln(1+x)\) is positive for all positive \(x\). \begin{align*} \sum_{k=1}^n \frac1k &\underbrace{>}_{x > \ln(1+x)} \sum_{k=1}^n \ln \left (1 + \frac1k \right ) \\ &= \sum_{k=1}^n \ln \left ( \frac{k+1}{k} \right ) \\ &= \sum_{k=1}^n \left ( \ln (k+1) - \ln (k) \right) \\ &= \ln (n+1) - \ln 1 \\ &= \ln (n+1) \end{align*}
  2. Let \(g(x) = x + \ln (1-x)\) ,then \(g'(x) = 1 - \frac{1}{1-x} = \frac{-x}{1-x} < 0\) if \(0 < x < 1\) and \(g(0) = 0\). Therefore \(g(x)\) is decreasing and hence negative on \(0 < x < 1\), in particular \(x < -\ln(1-x) \) \begin{align*} \sum_{k=2}^n \frac1{k^2} &\underbrace{<}_{x < -\ln(1+x)} \sum_{k=2}^n - \ln \left (1-\frac1{k^2} \right) \\ &= -\sum_{k=2}^n \ln \left ( \frac{k^2-1}{k^2}\right) \\ &= \sum_{k=2}^n \l 2 \ln k - \ln(k-1) - \ln(k+1) \r \\ &= \ln n - \ln(n+1) - \ln 0+\ln 2 \\ &= \ln 2 + \ln \frac{n}{n+1} \end{align*} as \(n \to \infty\) we must have \(\displaystyle \sum_{k=2}^{\infty} \frac1{k^2} < \ln 2\) ie \[ \sum_{k=1}^\infty \frac 1 {k^2} <1+ \ln 2\]

View
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
2008 Paper 3 Q13
D: 1700.0 B: 1500.0
probability expected value variance indicator random variables linearity of expectation harmonic series combinatorics discrete probability distributions

A box contains \(n\) pieces of string, each of which has two ends. I select two string ends at random and tie them together. This creates either a ring (if the two ends are from the same string) or a longer piece of string. I repeat the process of tying together string ends chosen at random until there are none left. Find the expected number of rings created at the first step and hence obtain an expression for the expected number of rings created by the end of the process. Find also an expression for the variance of the number of rings created. Given that \(\ln 20 \approx 3\) and that \(1+ \frac12 + \cdots + \frac 1n \approx \ln n\) for large \(n\), determine approximately the expected number of rings created in the case \(n=40\,000\).

Solution: Let \(X_i\) be the indicator variable a loop is formed when there are \(i\) strings in the bag, so \(\mathbb{P}(X_i = 1) = \frac{1}{2i-1}\). Therefore \begin{align*} && Y_n &= X_n + Y_{n-1} \\ && Y_n &= X_n + \cdots + X_1 \\ \Rightarrow && \E[Y_n] &= \frac{1}{2n-1} + \frac{1}{2n-3} + \cdots + \frac{1}{1} \\ && \var[Y_n] &= \sum_{i=1}^n \frac{1}{2i-1} \frac{2i-2}{2i-1} \\ &&&= 2\sum_{i=1}^n \frac{i-1}{(2i-1)^2} \end{align*} \begin{align*} && \E[Y_{n}] &= 1 + \frac13 + \cdots + \frac{1}{2n-1} \\ &&&= 1 + \frac12 + \cdots + \frac1{2n} - \frac12\left (1 + \frac12 + \cdots + \frac1n \right) \\ &&&\approx \ln 2n -\frac12 \ln n \\ &&&= \ln 2 \sqrt{n} \\ \\ && \E[Y_{40\,000}] &= \ln 2 \sqrt{40\,000} \\ &&&= \ln 400 \\ &&&= 2 \ln 20 \approx 6 \end{align*}

View
1999 Paper 1 Q8
D: 1500.0 B: 1500.0
integration inequality bounding integrals logarithm harmonic series divergence telescoping sum estimation

The function \(\f\) satisfies \(0\leqslant\f(t)\leqslant K\) when \(0\leqslant t\leqslant x\). Explain by means of a sketch, or otherwise, why \[0\leqslant\int_{0}^{x} \f (t)\,{\mathrm d}t \leqslant Kx.\] By considering \(\displaystyle \int_{0}^{1}\frac{t}{n(n-t)}\,{\mathrm d}t\), or otherwise, show that, if \(n>1\), \[ 0\le \ln \left( \frac n{n-1}\right) -\frac 1n \le \frac 1 {n-1} - \frac 1n \] and deduce that \[ 0\le \ln N -\sum_{n=2}^N \frac1n \le 1. \] Deduce that as \(N\to \infty\) \[ \sum_{n=1}^N \frac1n \to\infty. \] Noting that \(2^{10}=1024\), show also that if \(N<10^{30}\) then \[ \sum_{n=1}^N \frac1n <101. \]

View
1995 Paper 1 Q5
D: 1500.0 B: 1500.0
integration binomial coefficients differentiation substitution harmonic series polynomial definite integral geometric series

If \[ \mathrm{f}(x)=nx-\binom{n}{2}\frac{x^{2}}{2}+\binom{n}{3}\frac{x^{3}}{3}-\cdots+(-1)^{r+1}\binom{n}{r}\frac{x^{r}}{r}+\cdots+(-1)^{n+1}\frac{x^{n}}{n}\,, \] show that \[ \mathrm{f}'(x)=\frac{1-(1-x)^{n}}{x}\,. \] Deduce that \[ \mathrm{f}(x)=\int_{1-x}^{1}\frac{1-y^{n}}{1-y}\,\mathrm{d}y. \] Hence show that \[ \mathrm{f}(1)=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}\,. \]

Solution: \begin{align*} f(x) & =nx-\binom{n}{2}\frac{x^{2}}{2}+\binom{n}{3}\frac{x^{3}}{3}-\cdots+(-1)^{r+1}\binom{n}{r}\frac{x^{r}}{r}+\cdots+(-1)^{n+1}\frac{x^{n}}{n} \\ f'(x) &= n - \binom{n}{2} x + \binom{n}{3}x^2 - \cdots (-1)^{r+1} \binom{n}{r} + \cdots + (-1)^{n+1} x^{n-1} \\ &= \frac{1-(1-x)^n}{x} \end{align*} Therefore, since \(\displaystyle f(x) = \int_0^xf'(t)\,dt\) \begin{align*} f(x) &= \int_0^x \frac{1 - (1-t)^n}{t} \, dt \\ &= \int_{1}^{1-x} \frac{1-y^n}{1-y} (-1)\, dy \tag{Let \(y = 1-t, \frac{dy}{dt} = -1\)} \\ &= \boxed{\int_{1-x}^1 \frac{1-y^n}{1-y} dy} \\ &= \int_{1-x}^1 \l 1 + y + y^2 + \cdots + y^{n-1} \r \, dy \\ &= \left [ y + \frac{y^2}{2} + \frac{y^3}{3} + \cdots + \frac{y^n}{n} \right]_{1-x}^1 \\ \end{align*} So when \(x = 1, 1-x = 0\) so we exactly have the sum required.

View
1994 Paper 2 Q13
D: 1600.0 B: 1629.1
probability geometric distribution expected value coupon collector problem integration inequality harmonic series logarithm approximation

The makers of Cruncho (`The Cereal Which Cares') are giving away a series of cards depicting \(n\) great mathematicians. Each packet of Cruncho contains one picture chosen at random. Show that when I have collected \(r\) different cards the expected number of packets I must open to find a new card is \(n/(n-r)\) where \(0\leqslant r\leqslant n-1.\) Show by means of a diagram, or otherwise, that \[ \frac{1}{r+1}\leqslant\int_{r}^{r+1}\frac{1}{x}\,\mathrm{d}x\leqslant\frac{1}{r} \] and deduce that \[ \sum_{r=2}^{n}\frac{1}{r}\leqslant\ln n\leqslant\sum_{r=1}^{n-1}\frac{1}{r} \] for all \(n\geqslant2.\) My children will give me no peace until we have the complete set of cards, but I am the only person in our household prepared to eat Cruncho and my spouse will only buy the stuff if I eat it. If \(n\) is large, roughly how many packets must I expect to consume before we have the set?

View
1991 Paper 1 Q9
D: 1500.0 B: 1516.0
proof inequality exponentials harmonic series summation bounding arguments proof by contradiction

  1. Suppose that the real number \(x\) satisfies the \(n\) inequalities \begin{alignat*}{2} 1<\ & x & & < 2\\ 2<\ & x^{2} & & < 3\\ 3<\ & x^{3} & & < 4\\ & \vdots\\ n<\ & x^{n} & & < n+1 \end{alignat*} Prove without the use of a calculator that \(n\leqslant4\).
  2. If \(n\) is an integer strictly greater than 1, by considering how many terms there are in \[ \frac{1}{n+1}+\frac{1}{n+2}+\cdots+\frac{1}{n^{2}}, \] or otherwise, show that \[ \frac{1}{n}+\frac{1}{n+1}+\cdots+\frac{1}{n^{2}}>1. \] Hence or otherwise find, with justification, an integer \(N\) such that \({\displaystyle {\displaystyle \sum_{n=1}^{N}\frac{1}{n}>10.}}\)

Solution:

  1. Suppose \(n > 4\) then the following inequalities are both true \begin{align*} 3 < x^3 < 4 & \Rightarrow 3^5 < x^{15} < 4^{5}\\ 5 < x^5 < 6 & \Rightarrow 5^{3} < x^{15} < 6^3 \end{align*} But \(3^5 = 243\) and \(6^3 = 216\) so \(243 < x^{15} < 216\) whichis a contradiction.
  2. This question is wrong. Consider \(n = 2\), then \(\frac{1}{2+1} + \frac{1}{2+2} = \frac13+\frac14 = \frac{7}{12} < 1\). The question should be about \(n \geq 4\). \begin{align*} \frac{1}{n+1}+\frac1{n+2}+\cdots + \frac{1}{2n} > \frac{n}{2n} &= \frac12 \\ \frac{1}{2n+1}+\frac1{2n+2}+\cdots + \frac{1}{3n} > \frac{n}{3n} &= \frac13 \\ \frac{1}{4n+1}+\frac1{4n+2}+\cdots + \frac{1}{4n} > \frac{n}{4n} &= \frac14 \\ \sum_{k=1}^{n^2-n} \frac{1}{n+k} > \frac{13}{12} &> 1 \end{align*} We have a stronger result, \(\frac1{n+1} + \cdots + \frac1{4n} > 1\) for \(n > 4\) so we can take \(N = 4^{10}\) since, since there will be \(9\) sequences from \(\frac{1}{4^{i}+1} \to \frac{1}{4^{i+1}}\) and we will have \(\frac1{1}\) at the start to give use the extra \(1\).

View