Problems

Filters
Clear Filters

85 problems found

2025 Paper 2 Q4
D: 1500.0 B: 1500.0
proof by induction floor function integer part periodic function telescoping summation functional equation

Let \(\lfloor x \rfloor\) denote the largest integer that satisfies \(\lfloor x \rfloor \leq x\). For example, if \(x = -4.2\), then \(\lfloor x \rfloor = -5\).

  1. Show that, if \(n\) is an integer, then \(\lfloor x + n \rfloor = \lfloor x \rfloor + n\).
  2. Let \(n\) be a positive integer and define function \(f_n\) by \[f_n(x) = \lfloor x \rfloor + \left\lfloor x + \frac{1}{n} \right\rfloor + \left\lfloor x + \frac{2}{n} \right\rfloor + \ldots + \left\lfloor x + \frac{n-1}{n} \right\rfloor - \lfloor nx \rfloor\]
    1. Show that \(f_n\left(x + \frac{1}{n}\right) = f_n(x)\).
    2. Evaluate \(f_n(t)\) for \(0 \leq t < \frac{1}{n}\).
    3. Hence show that \(f_n(x) \equiv 0\).
    1. Show that \(\left\lfloor \frac{x}{2} \right\rfloor + \left\lfloor \frac{x+1}{2} \right\rfloor = \lfloor x \rfloor\).
    2. Hence, or otherwise, simplify \[\left\lfloor \frac{x+1}{2} \right\rfloor + \left\lfloor \frac{x+2}{2^2} \right\rfloor + \ldots + \left\lfloor \frac{x+2^k}{2^{k+1}} \right\rfloor + \ldots\]

Solution:

  1. Claim: If \(n \in \mathbb{Z}\) then \(\lfloor x + n \rfloor = \lfloor x \rfloor + n\) Proof: Since \(\lfloor x \rfloor \leq x\) then \(\lfloor x \rfloor + n \leq x + n\) and \(\lfloor x \rfloor + n \in \mathbb{Z}\) we must have that \(\lfloor x \rfloor +n \leq \lfloor x + n \rfloor\). However, since \(\lfloor x \rfloor + 1 > x\) we must also have that \(\lfloor x \rfloor + 1 + n > x + n\), therefore \(\lfloor x \rfloor + n\) is the largest integer less than \(x + n\) as required.
    1. Claim: \(f_n\left(x + \frac{1}{n}\right) = f_n(x)\) Proof: \begin{align*} f_n\left(x + \frac{1}{n}\right) &=\left \lfloor x+ \frac{1}{n} \right \rfloor + \left\lfloor x + \frac{1}{n}+ \frac{1}{n} \right\rfloor + \left\lfloor x+ \frac{1}{n} + \frac{2}{n} \right\rfloor + \ldots + \left\lfloor x+ \frac{1}{n} + \frac{n-1}{n} \right\rfloor - \left \lfloor n\left ( x + \frac{1}{n} \right) \right \rfloor \\ &= \left \lfloor x+ \frac{1}{n} \right \rfloor + \left\lfloor x + \frac{2}{n}\right\rfloor + \left\lfloor x+ \frac{3}{n} \right\rfloor + \ldots + \left\lfloor x+ \frac{n}{n} \right\rfloor - \left \lfloor nx + 1 \right \rfloor \\ &= \left \lfloor x+ \frac{1}{n} \right \rfloor + \left\lfloor x + \frac{2}{n}\right\rfloor + \left\lfloor x+ \frac{3}{n} \right\rfloor + \ldots + \left\lfloor x+ 1 \right\rfloor - \left \lfloor nx + 1 \right \rfloor \\ &= \left \lfloor x+ \frac{1}{n} \right \rfloor + \left\lfloor x + \frac{2}{n}\right\rfloor + \left\lfloor x+ \frac{3}{n} \right\rfloor + \ldots + \lfloor x \rfloor + 1 - \left ( \lfloor nx \rfloor + 1 \right) \\ &= \lfloor x \rfloor + \left\lfloor x + \frac{1}{n} \right\rfloor + \left\lfloor x + \frac{2}{n} \right\rfloor + \ldots + \left\lfloor x + \frac{n-1}{n} \right\rfloor - \lfloor nx \rfloor \\ &= f_n(x) \end{align*}
    2. Suppose \(0 \leq t < \frac1n\), then note that \(\left \lfloor t + \frac{k}{n} \right \rfloor = 0\) for \(0 \leq k \leq n - 1\) and \(\lfloor n t \rfloor = 0\) since \(nt < 1\)
    3. Since \(f_n(x)\) is zero on \([0, \tfrac1n)\) and periodic with period \(\tfrac1n\) it must be constantly zero
    1. Claim: \(\left\lfloor \frac{x}{2} \right\rfloor + \left\lfloor \frac{x+1}{2} \right\rfloor = \lfloor x \rfloor\) Proof: Suppose \(x = n + \epsilon\) where \(0 \leq \epsilon < 1\), ie \(n = \lfloor x \rfloor\), then consider two cases: Case 1: \(n = 2k\) \begin{align*} \left\lfloor \frac{x}{2} \right\rfloor + \left\lfloor \frac{x+1}{2} \right\rfloor &= \left\lfloor \frac{n + \epsilon}{2} \right\rfloor + \left\lfloor \frac{n + \epsilon+1}{2} \right\rfloor \\ &= \left\lfloor \frac{2k + \epsilon}{2} \right\rfloor + \left\lfloor \frac{2k + \epsilon+1}{2} \right\rfloor \\ &= k + \left\lfloor \frac{\epsilon}{2} \right\rfloor + k + \left\lfloor \frac{\epsilon+1}{2} \right\rfloor \\ &= 2k \\ &= n \end{align*} Case 2: \(n = 2k + 1\) \begin{align*} \left\lfloor \frac{x}{2} \right\rfloor + \left\lfloor \frac{x+1}{2} \right\rfloor &= \left\lfloor \frac{n + \epsilon}{2} \right\rfloor + \left\lfloor \frac{n + \epsilon+1}{2} \right\rfloor \\ &= \left\lfloor \frac{2k +1+ \epsilon}{2} \right\rfloor + \left\lfloor \frac{2k +1+ \epsilon+1}{2} \right\rfloor \\ &= k + \left\lfloor \frac{\epsilon+1}{2} \right\rfloor + k +1+ \left\lfloor \frac{\epsilon}{2} \right\rfloor \\ &= 2k +1\\ &= n \end{align*} as required.
    2. Since \(\left \lfloor \frac{x+1}{2} \right \rfloor = \lfloor x \rfloor - \lfloor \frac{x}{2} \rfloor\) and in general, \(\left \lfloor \frac{x+2^k}{2^{k+1}} \right \rfloor = \lfloor \frac{x}{2^k} \rfloor - \lfloor \frac{x}{2^{k+1}} \rfloor\) and so in general: \begin{align*} \sum_{k=0}^\infty \left \lfloor \frac{x+2^k}{2^{k+1}} \right \rfloor &= \sum_{k=0}^\infty \left ( \left \lfloor \frac{x}{2^k} \right \rfloor -\left \lfloor \frac{x}{2^{k+1}} \right \rfloor \right) \\ &= \lfloor x \rfloor \end{align*}

View
2025 Paper 3 Q8
D: 1500.0 B: 1500.0
complex numbers proof by induction De Moivre trig identity summation sin nθ cos nθ algebraic identity

  1. Show that $$z^{m+1} - \frac{1}{z^{m+1}} = \left(z - \frac{1}{z}\right)\left(z^m + \frac{1}{z^m}\right) + \left(z^{m-1} - \frac{1}{z^{m-1}}\right)$$ Hence prove by induction that, for \(n \geq 1\), $$z^{2n} - \frac{1}{z^{2n}} = \left(z - \frac{1}{z}\right)\sum_{r=1}^n \left(z^{2r-1} + \frac{1}{z^{2r-1}}\right)$$ Find similarly \(z^{2n} - \frac{1}{z^{2n}}\) as a product of \((z + \frac{1}{z})\) and a sum.
    1. By choosing \(z = e^{i\theta}\), show that $$\sin 2n\theta = 2\sin\theta \sum_{r=1}^n \cos(2r-1)\theta$$
    2. Use this result, with \(n = 2\), to show that \(\cos\frac{2\pi}{5} = \cos\frac{\pi}{5} - \frac{1}{2}\).
    3. Use this result, with \(n = 7\), to show that \(\cos\frac{2\pi}{15} + \cos\frac{4\pi}{15} + \cos\frac{8\pi}{15} + \cos\frac{16\pi}{15} = \frac{1}{2}\).
  3. Show that \(\sin\frac{\pi}{14} - \sin\frac{3\pi}{14} + \sin\frac{5\pi}{14} = \frac{1}{2}\).

Solution:

  1. \begin{align*} RHS &= \left(z - \frac{1}{z}\right)\left(z^m + \frac{1}{z^m}\right) + \left(z^{m-1} - \frac{1}{z^{m-1}}\right) \\ &= z^{m+1} + \frac{1}{z^{m-1}} - z^{m-1} - \frac{1}{z^{m+1}} + z^{m-1} - \frac{1}{z^{m-1}} \\ &= z^{m+1} - \frac{1}{z^{m+1}} \\ &= LHS \end{align*}. Claim: For \(n \geq 1\), $$z^{2n} - \frac{1}{z^{2n}} = \left(z - \frac{1}{z}\right)\sum_{r=1}^n \left(z^{2r-1} + \frac{1}{z^{2r-1}}\right)$$ Proof: (By Induction) Base Case: (\(n=1\)). \begin{align*} LHS &= z^2 - \frac{1}{z^2} \\ &= (z-\frac1z)(z + \frac{1}{z}) \\ &= (z - \frac1z) \sum_{r=1}^1 \left ( z + \frac{1}{z} \right) \\ &= (z - \frac1z) \sum_{r=1}^1 \left ( z^{2r-1} + \frac{1}{z^{2r-1}} \right) \\ &= RHS \end{align*} as required. Inductive step: Suppose our result is true for some \(n=k\), then consider \(n = k+1\). \begin{align*} RHS &= \left(z - \frac{1}{z}\right)\sum_{r=1}^{k+1} \left(z^{2r-1} + \frac{1}{z^{2r-1}}\right) \\ &= \left(z - \frac{1}{z}\right)\sum_{r=1}^{k} \left(z^{2r-1} + \frac{1}{z^{2r-1}}\right) + \left(z - \frac{1}{z}\right)\left(z^{2k+1} + \frac{1}{z^{2k+1}}\right) \\ &= z^{2k} - \frac{1}{z^{2k}} + \left(z - \frac{1}{z}\right)\left(z^{2k+1} + \frac{1}{z^{2k+1}}\right) \\ &= z^{2k+2} - \frac{1}{z^{2k+2}} \\ &= LHS \end{align*}. Therefore if our result is true for \(n=k\) is true, it is true for \(n=k+1\). Since it is also true for \(n=1\) it is true for all \(n \geq 1\) but the principle of mathematical induction. Since \(\displaystyle z^{m+1} - \frac{1}{z^{m+1}} = \left(z + \frac{1}{z}\right)\left(z^m - \frac{1}{z^m}\right) + \left(z^{m-1} - \frac{1}{z^{m-1}}\right)\), we must have \(\displaystyle z^{2n}-\frac{1}{z^{2n}} = \left ( z + \frac{1}{z} \right) \sum_{r=1}^n \left (z^{2r-1}-\frac{1}{z^{2r-1}} \right)\)
    1. Since $$z^{2n} - \frac{1}{z^{2n}} = \left(z - \frac{1}{z}\right)\sum_{r=1}^n \left(z^{2r-1} + \frac{1}{z^{2r-1}}\right)$$ we have \begin{align*} && e^{2n\theta i} - e^{-2n\theta i} &= \left(e^{\theta i} - e^{-\theta i}\right)\sum_{r=1}^n \left(e^{(2r-1)\theta i} + e^{-(2r-1)\theta i}\right) \\ \Rightarrow && 2i \sin 2n \theta &= 2i \sin \theta \sum_{r=1}^n 2 \cos (2r-1) \theta \\ \Rightarrow && \sin 2n \theta &= 2\sin \theta \sum_{r=1}^n \cos (2r-1) \theta \end{align*}
    2. When \(n = 2, \theta = \frac{\pi}{5}\) we have: \begin{align*} &&\sin \frac{4\pi}{5} &= 2 \sin \frac{\pi}{5} (\cos \frac{\pi}{5} + \cos \frac{3\pi}{5}) \\ &&\sin \frac{\pi}{5} &= 2 \sin \frac{\pi}{5} (\cos \frac{\pi}{5} - \cos \frac{2\pi}{5}) \\ &&\frac12 &= \cos \frac{\pi}{5} - \cos \frac{2 \pi}{5} \\ \Rightarrow && \cos \frac{2\pi}{5} &= \cos \frac{\pi}{5} - \frac12 \end{align*}
    3. When \(n = 7, \theta = \frac{\pi}{15}\) we have: \begin{align*} && \sin \frac{14 \pi}{15} &= 2 \sin \frac{\pi}{15} \sum_{r=1}^7 \cos (2r-1) \frac{\pi}{15} \\ \Rightarrow && \frac12 &= \cos \frac{\pi}{15} + \cos \frac{3 \pi}{15} + \cos \frac{5 \pi}{15}+ \cos \frac{7 \pi}{15}+ \cos \frac{9 \pi}{15}+ \cos \frac{11 \pi}{15}+ \cos \frac{13 \pi}{15} \\ &&&= -\cos \frac{16\pi}{15} + \cos \frac{3 \pi}{15} + \cos \frac{5 \pi}{15}- \cos \frac{8 \pi}{15}+ \cos \frac{9 \pi}{15}- \cos \frac{4 \pi}{15}- \cos \frac{2\pi}{15} \\ &&&= - \left ( \cos \frac{2\pi}{15}+\cos \frac{4\pi}{15}+\cos \frac{8\pi}{15}+\cos \frac{16\pi}{15}\right) + \cos \frac{\pi}{5} + \cos \frac{\pi}{3} + \cos \frac{3 \pi}{5} \\ &&&= - \left ( \cos \frac{2\pi}{15}+\cos \frac{4\pi}{15}+\cos \frac{8\pi}{15}+\cos \frac{16\pi}{15}\right) + \frac12 + \frac12 \\ \Rightarrow && \frac12 &= cos \frac{2\pi}{15}+\cos \frac{4\pi}{15}+\cos \frac{8\pi}{15}+\cos \frac{16\pi}{15} \end{align*}
  3. By using \(z = e^{i \theta}\) we have that: \begin{align*} && z^{2n}-\frac{1}{z^{2n}} &= \left ( z + \frac{1}{z} \right) \sum_{r=1}^n \left (z^{2r-1}-\frac{1}{z^{2r-1}} \right ) \\ \Rightarrow && e^{2n \theta i} - e^{-2n \theta i} &= (e^{\theta i} + e^{-\theta i}) \sum_{r=1}^n (e^{(2r-1)\theta i} - e^{(2r-1) \theta i}) \\ \Rightarrow && 2i \sin 2n \theta &= 2 \cos \theta \sum_{r=1}^n 2i \sin(2r-1) \theta \\ \Rightarrow && \sin 2n \theta &= 2 \cos \theta \sum_{r=1}^n \sin(2r-1) \theta \end{align*} When \(n = 3, \theta = \frac{\pi}{14}\) we must have: \begin{align*} &&\sin \frac{3 \pi}{7} &= 2 \cos \frac{\pi}{14}( \sin \frac{\pi}{14}+\sin \frac{3\pi}{14}+\sin \frac{5\pi}{14}) \\ &&&= 2 \sin \left (\frac{\pi}{2} - \frac{\pi}{14} \right)( \sin \frac{\pi}{14}+\sin \frac{3\pi}{14}+\sin \frac{5\pi}{14}) \\ &&&= 2 \sin \frac{3\pi}{7} ( \sin \frac{\pi}{14}+\sin \frac{3\pi}{14}+\sin \frac{5\pi}{14}) \\ \Rightarrow && \frac12 &= \sin \frac{\pi}{14}+\sin \frac{3\pi}{14}+\sin \frac{5\pi}{14} \end{align*} as required.

View
2024 Paper 3 Q1
D: 1500.0 B: 1500.0
sequences and series partial fractions telescoping series algebraic identity infinite series summation

Throughout this question, \(N\) is an integer with \(N \geqslant 1\) and \(S_N = \displaystyle\sum_{r=1}^{N} \frac{1}{r^2}\). You may assume that \(\displaystyle\lim_{N\to\infty} S_N\) exists and is equal to \(\frac{1}{6}\pi^2\).

  1. Show that \[\frac{1}{r+1} - \frac{1}{r} + \frac{1}{r^2} = \frac{1}{r^2(r+1)}.\] Hence show that \[\sum_{r=1}^{N} \frac{1}{r^2(r+1)} = \sum_{r=1}^{N} \frac{1}{r^2} - 1 + \frac{1}{N+1}.\] Show further that \(\displaystyle\sum_{r=1}^{\infty} \frac{1}{r^2(r+1)} = \frac{1}{6}\pi^2 - 1\).
  2. Find \(\displaystyle\sum_{r=1}^{N} \frac{1}{r^2(r+1)(r+2)}\) in terms of \(S_N\), and hence evaluate \(\displaystyle\sum_{r=1}^{\infty} \frac{1}{r^2(r+1)(r+2)}\).
  3. Show that \[\sum_{r=1}^{\infty} \frac{1}{r^2(r+1)^2} = \sum_{r=1}^{\infty} \frac{2}{r^2(r+1)} - 1.\]

Solution:

  1. \(\,\) \begin{align*} && \frac1{r+1} - \frac1r + \frac1{r^2} &= \frac{-1}{r(r+1)} + \frac{1}{r^2} \\ &&&= \frac{r+1-r}{r^2(r+1)} \\ &&&= \frac{1}{r^2(r+1)} \end{align*} Therefore \begin{align*} && \sum_{r=1}^N \frac1{r^2(r+1)} &= \sum_{r=1}^N \left (\frac1{r+1} - \frac1r + \frac1{r^2} \right) \\ &&&= \sum_{r=1}^N \left (\frac1{r+1} - \frac1r\right) + \sum_{r=1}^N \frac1{r^2} \\ &&&=\frac{1}{N+1} - 1 + \sum_{r=1}^N \frac1{r^2} \\ \end{align*} therefore \begin{align*} && \sum_{r=1}^{\infty} \frac{1}{r^2(r+1)} &= \lim_{N \to \infty } \sum_{r=1}^{N} \frac{1}{r^2(r+1)} \\ &&&= \lim_{N \to \infty } \left (\frac{1}{N+1} - 1 + \sum_{r=1}^N \frac1{r^2} \right) \\ &&&= -1 +\lim_{N \to \infty } \sum_{r=1}^N \frac1{r^2} \\ &&&= -1 + \sum_{r=1}^\infty \frac1{r^2} \\ &&&= \frac{\pi^2}{6}-1 \end{align*}
  2. Note that \begin{align*} && \frac{1}{r^2(r+1)(r+2)} &= \frac{Ar+B}{r^2} + \frac{C}{r+1} + \frac{D}{r+2} \\ &&&= \frac{1}{2r^2} + \frac{1}{r+1} - \frac{1}{4(r+2)} - \frac{3}{4r} \end{align*} So \begin{align*} && \sum_{r=1}^N \frac{1}{r^2(r+1)(r+2)} &= \sum_{r=1}^N \left ( \frac{1}{2r^2} + \frac{1}{r+1} - \frac{1}{4(r+2)} - \frac{3}{4r} \right ) \\ &&&= \frac12 \sum_{r=1}^N \frac{1}{r^2} + \frac{1}{2} - \frac14 \cdot \frac1{3} - \frac34 \frac11 + \\ &&& \quad \quad \quad + \frac13 - \frac14\frac14 - \frac34\frac12 + \\ &&& \quad \quad \quad + \frac14 - \frac14\frac15 - \frac34\frac13 + \\ &&&\quad \quad \quad+ \cdots + \\ &&&\quad \quad \quad + \frac1{N+1} - \frac14\frac1{N+2} - \frac34\frac1N \\ &&&= \frac12 \sum_{r=1}^N \frac{1}{r^2} +\frac14\frac12 - \frac34\frac11-\frac14\frac1{N+2}+\frac34 \frac1{N+1} \\ \\ \Rightarrow && \sum_{r=1}^{\infty} \frac{1}{r^2(r+1)(r+2)} &= \lim_{N \to \infty} \left [ \frac12 \sum_{r=1}^N \frac{1}{r^2} +\frac14\frac12 - \frac34\frac11-\frac14\frac1{N+2}+\frac34 \frac1{N+1}\right] \\ &&&= \frac{\pi^2}{12} -\frac58 \end{align*}
  3. Notice that \(\frac{1}{r^2(r+1)^2} - \frac{2}{r^2(r+1)} = \frac{1-2(r+1)}{r^2(r+1)^2} = \frac{-1-2r}{r^2(r+1)^2} = \frac{1}{(r+1)^2} - \frac{1}{r^2}\) and so \begin{align*} && \sum_{r=1}^N \frac{1}{r^2(r+1)^2} &= \sum_{r=1}^N \left ( \frac{2}{r^2(r+1)} +\frac{1}{(r+1)^2} - \frac{1}{r^2} \right) \\ &&&= \sum_{r=1}^N \frac{2}{r^2(r+1)} +\frac{1}{(N+1)^2} - 1 \\ \end{align*} and the result follows as \(N \to \infty\)
[There is a beautiful paper by KConrad about this question: https://kconrad.math.uconn.edu/blurbs/analysis/series_acceleration.pdf]

View
2019 Paper 2 Q11
D: 1500.0 B: 1500.0
probability combinatorics triangle inequality counting summation uniform distribution discrete random variables

  1. The three integers \(n_1\), \(n_2\) and \(n_3\) satisfy \(0 < n_1 < n_2 < n_3\) and \(n_1 + n_2 > n_3\). Find the number of ways of choosing the pair of numbers \(n_1\) and \(n_2\) in the cases \(n_3 = 9\) and \(n_3 = 10\). Given that \(n_3 = 2n + 1\), where \(n\) is a positive integer, write down an expression (which you need not prove is correct) for the number of ways of choosing the pair of numbers \(n_1\) and \(n_2\). Simplify your expression. Write down and simplify the corresponding expression when \(n_3 = 2n\), where \(n\) is a positive integer.
  2. You have \(N\) rods, of lengths \(1, 2, 3, \ldots, N\) (one rod of each length). You take the rod of length \(N\), and choose two more rods at random from the remainder, each choice of two being equally likely. Show that, in the case \(N = 2n + 1\) where \(n\) is a positive integer, the probability that these three rods can form a triangle (of non-zero area) is $$\frac{n - 1}{2n - 1}.$$ Find the corresponding probability in the case \(N = 2n\), where \(n\) is a positive integer.
  3. You have \(2M + 1\) rods, of lengths \(1, 2, 3, \ldots, 2M + 1\) (one rod of each length), where \(M\) is a positive integer. You choose three at random, each choice of three being equally likely. Show that the probability that the rods can form a triangle (of non-zero area) is $$\frac{(4M + 1)(M - 1)}{2(2M + 1)(2M - 1)}.$$ Note: \(\sum_{k=1}^{K} k^2 = \frac{1}{6}K(K + 1)(2K + 1)\).

Solution:

  1. If \(n_3 = 9\) and we are looking for \(0 < n_1 < n_2 < n_3\) we can consider values for each \(n_2\). \begin{array}{clc|c} n_2 & \text{range} & \text{count} \\ \hline 6 & 4-5 & 2 \\ 7 & 3-6 & 4 \\ 8 & 2-7 & 6 \\ \hline & & 12 \end{array} When \(n_3 = 10\) \begin{array}{clc|c} n_2 & \text{range} & \text{count} \\ \hline 6 & 5 & 1 \\ 7 & 4-6 & 3 \\ 8 & 3-7 & 5 \\ 9 & 2-8 & 7 \\ \hline & & 16 \end{array} When \(n_3 = 2n+1\) we can have \(2 + 4 + \cdots + 2n-2 = n(n-1)\) When \(n_3 = 2n\) we can have \(1 + 3 + \cdots + 2n-3 = (n-1)^2\)
  2. For the 3 rods to form a triangle, it suffices for the sum of the lengths of the shorter rods to be larger than \(N\). When \(N = 2n+1\) there are \(n(n-1)\) ways this can happen, out of \(\binom{2n}{2}\) ways to choos the numbers, ie \begin{align*} && P &= \frac{n(n-1)}{\frac{2n(2n-1)}{2}} \\ &&&= \frac{n-1}{2n-1} \end{align*} When \(N = 2n\) there are \((n-1)^2\) ways this can happen, out of \(\binom{2n-1}{2}\) ways, ie \begin{align*} && P &= \frac{(n-1)^2}{\frac{(2n-1)(2n-2)}{2}} \\ &&&= \frac{n-1}{2n-1} \end{align*}
  3. The number of ways this can happen is: \begin{align*} C &= \sum_{k=3}^{2M+1} \# \{ \text{triangles where }k\text{ is largest} \} \\ &= \sum_{k=1}^{M} \# \{ \text{triangles where }2k+1\text{ is largest} \} +\sum_{k=1}^{M} \# \{ \text{triangles where }2k\text{ is largest} \}\\ &= \sum_{k=1}^{M} n(n-1)+\sum_{k=1}^{M} (n-1)^2\\ &= \sum_{k=1}^{M} (2n^2-3n+1)\\ &= \frac26M(M+1)(2M+1) - \frac32M(M+1) + M \\ &= \frac16 M(4M+1)(M-1) \end{align*} Therefore the probability is \begin{align*} && P &= \frac{M(4M+1)(M-1)}{6 \binom{2M+1}{3}} \\ &&&= \frac{M(4M+1)(M-1)}{(2M+1)2M(2M-1)} \\ &&&= \frac{(4M+1)(M-1)}{2(2M+1)(2M-1)} \end{align*}

View
2017 Paper 2 Q6
D: 1600.0 B: 1484.8
proof by induction inequality summation sequences square root optimisation algebraic manipulation

Let \[ S_n = \sum_{r=1}^n \frac 1 {\sqrt r \ } \,, \] where \(n\) is a positive integer.

  1. Prove by induction that \[ S_n \le 2\sqrt n -1\, . \]
  2. 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 \,.\]

Solution:

  1. 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}\)
  2. 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\)

View
2017 Paper 3 Q1
D: 1700.0 B: 1516.0
sequences series binomial coefficients telescoping series inequality summation proof partial fractions convergence bounding sums

  1. Prove that, for any positive integers \(n\) and \(r\), \[ \frac{1}{^{n+r}\C_{r+1}} =\frac{r+1}{r} \left(\frac{1}{^{n+r-1}\C_{r}}-\frac{1}{^{n+r}\C_{r}}\right). \] Hence determine \[ \sum_{n=1}^{\infty}{\frac{1}{^{n+r}\C_{r+1}}} \,, \] and deduce that \ \(\displaystyle \sum_{n=2}^\infty \frac 1 {^{n+2}\C_3} = \frac12\,\).
  2. Show that, for \(n \ge 3\,\), \[ \frac{3!}{n^3} < \frac{1}{^{n+1}\C_{3}} \ \ \ \ \ \text{and} \ \ \ \ \ \frac{20}{^{n+1}\C_3} - \frac{1}{^{n+2}\C_{5}} < \frac{5!}{n^3} \,. \] By summing these inequalities for \(n \ge 3\,\), show that \[ \frac{115}{96} < \sum_{n=1}^{\infty}{\frac{1}{n^3}} < \frac{116}{96} \, . \]
{\bf Note: } \(^n\C_r\) is another notation for \(\displaystyle \binom n r \).

Solution: \begin{align*} \frac{r+1}{r} \left(\frac{1}{^{n+r-1}\C_{r}}-\frac{1}{^{n+r}\C_{r}}\right) &= \frac{r+1}{r} \l \frac{r!(n-1)!}{(n+r-1)!} - \frac{r!n!}{(n+r)!} \r \\ &= \frac{(r+1)!(n-1)!}{r(n+r-1)!} \l 1 - \frac{n}{n+r} \r \\ &= \frac{(r+1)!(n-1)!}{r(n+r-1)!} \frac{r}{n+r} \\ &= \frac{(r+1)!n!}{(n+r)!} \\ &= \frac{1}{^{n+r}\C_{r+1}} \end{align*} \begin{align*} \sum_{n=1}^{\infty}{\frac{1}{^{n+r}\C_{r+1}}} &= \sum_{n=1}^{\infty} \l \frac{r+1}{r} \left(\frac{1}{^{n+r-1}\C_{r}}-\frac{1}{^{n+r}\C_{r}}\right) \r \\ &= \frac{r+1}{r} \sum_{n=1}^{\infty} \l \frac{1}{^{n+r-1}\C_{r}}-\frac{1}{^{n+r}\C_{r}} \r \\ &= \frac{r+1}{r} \lim_{N \to \infty} \sum_{n=1}^{N} \l \frac{1}{^{n+r-1}\C_{r}}-\frac{1}{^{n+r}\C_{r}} \r \\ &= \frac{r+1}{r} \lim_{N \to \infty} \l \frac{1}{^{1+r-1}\C_{r}} - \frac{1}{^{N+r}\C_{r}}\r \\ &= \frac{r+1}{r} \frac{1}{^{1+r-1}\C_{r}} \tag{since \(\frac{1}{^{N+r}\C_{r}} \to 0\)} \\ &= \frac{r+1}{r} \end{align*} When \(r = 2\), we have: \begin{align*} && \frac{3}{2} &= \sum_{n=1}^{\infty}{\frac{1}{^{n+2}\C_{3}}} \\ && &=\frac{1}{^{1+2}\C_{3}} + \sum_{n=2}^{\infty}{\frac{1}{^{n+2}\C_{3}}} \\ && &= 1 + \sum_{n=2}^{\infty}{\frac{1}{^{n+2}\C_{3}}} \\ \Rightarrow && \sum_{n=2}^{\infty}{\frac{1}{^{n+2}\C_{3}}} &= \frac12 \end{align*} \begin{align*} \frac{1}{^{n+1}\C_{3}} &= \frac{3!}{(n+1)n(n-1)} \\ &= \frac{3!}{n^3-n} \\ &> \frac{3!}{n^3} \end{align*} \begin{align*} \frac{20}{^{n+1}\C_3} - \frac{1}{^{n+2}\C_{5}} &= \frac{5!}{(n+1)n(n-1)} - \frac{5!}{(n+2)(n+1)n(n-1)(n-2)} \\ &= \frac{5!}{n^3} \frac{n^2}{n^2-1}\l 1- \frac{1}{n^2-4} \r \\ &= \frac{5!}{n^3} \frac{n^2}{n^2-1}\l \frac{n^2-5}{n^2-4} \r \\ &= \frac{5!}{n^3} \frac{n^2(n^2-5)}{(n^2-1)(n^2-4)} \\ &< \frac{5!}{n^3} \end{align*} Since \(k(k-5) < (k-1)(k-4) \Leftrightarrow 0 < 4\), this only makes sense if \(n \geq 3\) \begin{align*} &&\frac{3!}{n^3} &< \frac{1}{^{n+1}\C_{3}} \tag{if \(n \geq 3\)} \\ \Rightarrow &&\sum_{n=3}^\infty \frac{3!}{n^3} &< \sum_{n=3}^\infty \frac{1}{^{n+1}\C_{3}} \\ \Rightarrow && \frac{6}{1^3} + \frac{6}{2^3} + \sum_{n=3}^\infty \frac{3!}{n^3} &< \frac{6}{1^3} + \frac{6}{2^3} + \sum_{n=3}^\infty \frac{1}{^{n+1}\C_{3}} \\ \Rightarrow && \sum_{n=1}^\infty \frac{3!}{n^3} &< 6 + \frac{3}{4} + \sum_{n=2}^\infty \frac{1}{^{n+2}\C_{2+1}} \\ \Rightarrow && \sum_{n=1}^\infty \frac{3!}{n^3} &< 6 + \frac{3}{4} + \frac{1}{2} = \frac{29}{4} \\ \Rightarrow && \sum_{n=1}^\infty \frac{1}{n^3} &< \frac{29}{24} = \frac{116}{96} \\ \end{align*} \begin{align*} && \frac{20}{^{n+1}\C_3} - \frac{1}{^{n+2}\C_{5}} &< \frac{5!}{n^3} \\ \Rightarrow && \sum_{n=3}^\infty \l \frac{20}{^{n+1}\C_3} - \frac{1}{^{n+2}\C_{5}} \r &< \sum_{n=3}^\infty \frac{5!}{n^3} \\ \Rightarrow && \frac{120}{1^3} + \frac{120}{2^3} + \sum_{n=3}^\infty \frac{20}{^{n+1}\C_3} - \sum_{n=3}^\infty \frac{1}{^{n+2}\C_{5}} &< \frac{120}{1^3} + \frac{120}{2^3} + \sum_{n=3}^\infty \frac{5!}{n^3} \\ \Rightarrow && \frac{120}{1^3} + \frac{120}{2^3} + \sum_{n=2}^\infty \frac{20}{^{n+2}\C_{2+1}} - \sum_{n=1}^\infty \frac{1}{^{n+4}\C_{4+1}} &< \frac{120}{1^3} + \frac{120}{2^3} + \sum_{n=3}^\infty \frac{5!}{n^3} \\ \Rightarrow && \frac{120}{1^3} + \frac{120}{2^3} + \frac{20}{2} - \frac{4+1}{4} &< \sum_{n=1}^\infty \frac{5!}{n^3} \\ \Rightarrow && \frac{115}{96} &< \sum_{n=1}^\infty \frac{1}{n^3} \\ \end{align*}

View
2017 Paper 3 Q12
D: 1700.0 B: 1500.2
probability joint distribution marginal distribution independence covariance discrete random variables bivariate data summation

The discrete random variables \(X\) and \(Y\) can each take the values \(1\), \(\ldots\,\), \(n\) (where \(n\ge2\)). Their joint probability distribution is given by \[ \P(X=x, \ Y=y) = k(x+y) \,, \] where \(k\) is a constant.

  1. Show that \[ \P(X=x) = \dfrac{n+1+2x}{2n(n+1)}\,. \] Hence determine whether \(X\) and \(Y\) are independent.
  2. Show that the covariance of \(X\) and \(Y\) is negative.

Solution:

  1. \(\,\) \begin{align*} && \mathbb{P}(X = x) &= \sum_{y=1}^n \mathbb{P}(X=x,Y=y) \\ &&&= \sum_{y=1}^n k(x+y) \\ &&&= nkx + k\frac{n(n+1)}2 \\ \\ && 1 &= \sum_{x=1}^n \mathbb{P}(X=x) \\ &&&= nk\frac{n(n+1)}{2} + kn\frac{n(n+1)}2 \\ &&&= kn^2(n+1) \\ \Rightarrow && k &= \frac{1}{n^2(n+1)} \\ \Rightarrow && \mathbb{P}(X = x) &= \frac{nx}{n^2(n+1)} + \frac{n(n+1)}{2n^2(n+1)} \\ &&&= \frac{n+1+2x}{2n(n+1)} \\ \\ && \mathbb{P}(X=x)\mathbb{P}(Y=y) &= \frac{(n+1)^2+2(n+1)(x+y)+4xy}{4n^2(n+1)^2} \\ &&&\neq \frac{x+y}{n^2(n+1)} \end{align*} Therefore \(X\) and \(Y\) are not independent.
  2. \(\,\) \begin{align*} && \E[X] &= \sum_{x=1}^n x \mathbb{P}(X=x) \\ &&&= \sum_{x=1}^n x \mathbb{P}(X=x)\\ &&&= \sum_{x=1}^n x \frac{n+1+2x}{2n(n+1)} \\ &&&= \frac{1}{2n(n+1)} \left ( (n+1) \sum x + 2\sum x^2\right)\\ &&&= \frac{1}{2n(n+1)} \left ( \frac{n(n+1)^2}{2} + \frac{n(n+1)(2n+1)}{3} \right) \\ &&&= \frac{1}{2} \left ( \frac{n+1}{2} + \frac{2n+1}{3} \right)\\ &&&= \frac{1}{2} \left ( \frac{7n+5}{6} \right)\\ &&&= \frac{7n+5}{12} \\ \\ && \textrm{Cov}(X,Y) &= \mathbb{E}\left[XY\right] - \E[X] \E[Y] \\ &&&= \sum_{x=1}^n \sum_{y=1}^n xy \frac{x+y}{n^2(n+1)} - \E[X]^2 \\ &&&= \frac{1}{n^2(n+1)} \sum \sum (x^2 y+xy^2) - \E[X]^2 \\ &&&= \frac{1}{n^2(n+1)} \left (\sum y \right )\left (\sum x^2\right ) - \E[X]^2 \\ &&&=\frac{(n+1)(2n+1)}{12} - \left ( \frac{7n+5}{12}\right)^2 \\ &&&= \frac1{144} \left (12(2n^2+3n+1) - (49n^2+70n+25) \right)\\ &&&= \frac{1}{144} \left (-25n^2-34n-13 \right) \\ &&& < 0 \end{align*} since \(\Delta = 34^2 - 4 \cdot 25 \cdot 13 = 4(17^2-25 \times 13) = -4 \cdot 36 < 0\)

View
2016 Paper 2 Q5
D: 1600.0 B: 1484.0
generalised binomial theorem binomial expansion combinatorial identity summation Vandermonde identity negative binomial proof binomial coefficients

In this question, the definition of \(\displaystyle\binom pq\) is taken to be \[ \binom pq = \begin{cases} \dfrac{p!}{q!(p-q)!} & \text{ if } p\ge q\ge0 \,,\\[4mm] 0 & \text{ otherwise } . \end{cases} \]

  1. Write down the coefficient of \(x^n\) in the binomial expansion for \((1-x)^{-N}\), where \(N\) is a positive integer, and write down the expansion using the \(\Sigma\) summation notation. By considering $ (1-x)^{-1} (1-x)^{-N} \, ,$ where \(N\) is a positive integer, show that \[ \sum_{j=0}^n \binom { N+j -1}{j} = \binom{N+n}{n}\,. \]
  2. Show that, for any positive integers \(m\), \(n\) and \(r\) with \(r\le m+n\), \[ \binom{m+n} r = \sum _{j=0}^r \binom m j \binom n {r-j} \,. \]
  3. Show that, for any positive integers \(m\) and \(N\), \[ \sum_{j=0}^n(-1)^{j} \binom {N+m} {n-j} \binom {m+j-1}{j } = \displaystyle \binom N n . \]

Solution:

  1. \(\frac{(-N)(-N-1)\cdots(-N-n+1)}{n!} = \binom{N+n-1}{n}\), so \[ (1-x)^{-N} = \sum_{n=0}^{\infty} \binom{N+n-1}{n} x^n\] \begin{align*} && (1-x)^{-N-1} &= (1-x)^{-1}(1-x)^{-N} \\ &&&= (1 + x + x^2 + \cdots)\left ( \sum_{n=0}^{\infty} \binom{N+n-1}{n} x^n\right)\\ [x^{n}]: && \binom{N+1+n-1}{n} &= \sum_{j=0}^n \underbrace{1}_{x^{n-j} \text{ from 1st bracket}}\cdot\underbrace{\binom{N+j-1}{j}}_{x^j\text{ from second bracket}} \\ \Rightarrow && \binom{N+n}{n} &= \sum_{j=0}^n \binom{N+j-1}{j} \end{align*}
  2. Consider \((1+x)^{m+n} = (1+x)^m(1+x)^n\) and consider the coefficient of \(x^r\) from each side. On the left hand side this is clearly \(\binom{m+n}{r}\) on the right hand side we can take \(x^j\) from \((1+x)^m\) and \(x^{n-j}\) from \((1+x)^n\) and \(j\) can take any value from \(0\) to \(r\), ie \[ \binom{m+n} r = \sum _{j=0}^r \binom m j \binom n {r-j} \]
  3. Consider \((1-x)^{-(N+m+1)} = (\)

View
2016 Paper 3 Q12
D: 1700.0 B: 1516.0
Chebyshev's inequality Poisson distribution binomial distribution probability bounds inequality mean and variance summation

Let \(X\) be a random variable with mean \(\mu\) and standard deviation \(\sigma\). Chebyshev's inequality, which you may use without proof, is \[ \P\left(\vert X-\mu\vert > k\sigma\right) \le \frac 1 {k^2} \,, \] where \(k\) is any positive number.

  1. The probability of a biased coin landing heads up is \(0.2\). It is thrown \(100n\) times, where \(n\) is an integer greater than 1. Let \(\alpha \) be the probability that the coin lands heads up \(N\) times, where \(16n \le N \le 24n\). Use Chebyshev's inequality to show that \[ \alpha \ge 1-\frac 1n \,. \]
  2. Use Chebyshev's inequality to show that \[ 1+ n + \frac{n^2}{ 2!} + \cdots + \frac {n^{2n}}{(2n)!} \ge \left(1-\frac1n\right) \e^n \,. \]

Solution:

  1. Let \(N\) be the number of times the coin lands heads up, ie \(N \sim Binomial(100n, 0.2)\), then \(\mathbb{E}(N) = \mu = 20n, \mathrm{Var}(N) = \sigma^2 = 100n \cdot 0.2 \cdot 0.8 = 16n \Rightarrow \sigma = 4\sqrt{n}\). \begin{align*} && \mathbb{P}(|X - \mu| > k\sigma) &\leq \frac{1}{k^2} \\ \Rightarrow && 1 - \mathbb{P}(|X - \mu| \leq k\sigma) &\leq \frac1{k^2} \\ \Rightarrow && 1 - \mathbb{P}(|X - 20n| \leq \sqrt{n} \cdot 4\sqrt{n}) &\leq \frac1{{\sqrt{n}}^2} \\ \Rightarrow && 1 - \mathbb{P}(16n \leq N \leq 24n) &\leq \frac{1}{n} \\ \Rightarrow && 1 - \frac1n &\leq \alpha \end{align*}
  2. Suppose \(X \sim Pois(n)\), then \(\mathbb{E}(X) = n, \mathrm{Var}(X) = n\). Therefore \begin{align*} && \mathbb{P}(|X - \mu| > k\sigma) &\leq \frac{1}{k^2} \\ \Rightarrow && 1-\mathbb{P}(|X - n| \leq \sqrt{n} \cdot \sqrt{n}) &> \frac{1}{\sqrt{n}^2} \\ \Rightarrow && 1 - \sum_{i=0}^{2n} \mathbb{P}(X = i) & \leq \frac{1}{n} \\ \Rightarrow && \sum_{i=0}^{2n} e^{-n} \frac{n^i}{i!} \geq 1 - \frac{1}{n} \\ \Rightarrow && \sum_{i=0}^{2n} \frac{n^i}{i!} \geq \left ( 1 - \frac1n \right)e^n \end{align*}

View
2016 Paper 3 Q13
D: 1700.0 B: 1500.0
kurtosis normal distribution integration expectation summation independent random variables fourth moment proof

Given a random variable \(X\) with mean \(\mu\) and standard deviation \(\sigma\), we define the kurtosis, \(\kappa\), of \(X\) by \[ \kappa = \frac{ \E\big((X-\mu)^4\big)}{\sigma^4} -3 \,. \] Show that the random variable \(X-a\), where \(a\) is a constant, has the same kurtosis as \(X\).

  1. Show by integration that a random variable which is Normally distributed with mean 0 has kurtosis 0.
  2. Let \(Y_1, Y_2, \ldots, Y_n\) be \(n\) independent, identically distributed, random variables with mean 0, and let \(T = \sum\limits_{r=1}^n Y_r\). Show that \[ \E(T^4) = \sum_{r=1}^n \E(Y_r^4) + 6 \sum_{r=1}^{n-1} \sum_{s=r+1}^{n} \E(Y^2_s) \E(Y^2_r) \,. \]
  3. Let \(X_1\), \(X_2\), \(\ldots\)\,, \(X_n\) be \(n\) independent, identically distributed, random variables each with kurtosis \(\kappa\). Show that the kurtosis of their sum is \(\dfrac\kappa n\,\).

Solution: \begin{align*} &&\kappa_{X-a} &= \frac{\mathbb{E}\left(\left(X-a-(\mu-a)\right)^4\right)}{\sigma_{X-a}^4}-3 \\ &&&= \frac{\mathbb{E}\left(\left(X-\mu\right)^4\right)}{\sigma_X^4}-3\\ &&&= \kappa_X \end{align*}

  1. \(\,\) \begin{align*} && \kappa &= \frac{\mathbb{E}((X-\mu)^4)}{\sigma^4} - 3 \\ &&&= \frac{\mathbb{E}((\mu+\sigma Z-\mu)^4)}{\sigma^4} - 3 \\ &&&= \frac{\mathbb{E}((\sigma Z)^4)}{\sigma^4} - 3 \\ &&&= \mathbb{E}(Z^4)-3\\ &&&= \int_{-\infty}^{\infty} x^4\frac{1}{\sqrt{2\pi}} \exp \left ( - \frac12x^2 \right)\d x -3 \\ &&&= \left [\frac{1}{\sqrt{2\pi}}x^{3} \cdot \left ( -\exp \left ( - \frac12x^2 \right)\right) \right]_{-\infty}^{\infty} + \frac{1}{\sqrt{2\pi}} \int_{-\infty}^\infty 3x^2 \exp \left ( - \frac12x^2 \right) \d x - 3 \\ &&&= 0 + 3 \textrm{Var}(Z) - 3 =0 \end{align*}
  2. \(\,\) \begin{align*} && \mathbb{E}(T^4) &= \mathbb{E} \left [\left ( \sum\limits_{r=1}^n Y_r\right)^4\right] \\ &&&= \mathbb{E} \left [ \sum_{r=1}^n Y_r^4+\sum_{i\neq j} 4Y_iY_j^3+\sum_{i\neq j} 6Y_i^2Y_j^2+\sum_{i\neq j \neq k} 12Y_iY_jY_k^2 +\sum_{i\neq j\neq k \neq l}24 Y_iY_jY_kY_l\right] \\ &&&= \sum_{r=1}^n \mathbb{E} \left [ Y_r^4 \right]+\sum_{i\neq j} \mathbb{E} \left [ 4Y_iY_j^3\right]+\sum_{i\neq j} \mathbb{E} \left [ 6Y_i^2Y_j^2\right]+\sum_{i\neq j \neq k} \mathbb{E} \left [ 12Y_iY_jY_k^2\right] +\sum_{i\neq j\neq k \neq l} \mathbb{E} \left [ 24 Y_iY_jY_kY_l\right] \\ &&&= \sum_{r=1}^n \mathbb{E} \left [ Y_r^4 \right]+4\sum_{i\neq j} \mathbb{E} \left [ Y_i]\mathbb{E}[Y_j^3\right]+6\sum_{i\neq j} \mathbb{E} \left [ Y_i^2]\mathbb{E}[Y_j^2\right]+12\sum_{i\neq j \neq k} \mathbb{E} \left [ Y_i]\mathbb{E}[Y_j]\mathbb{E}[Y_k^2\right] +24\sum_{i\neq j\neq k \neq l} \mathbb{E} \left [ Y_i]\mathbb{E}[Y_j]\mathbb{E}[Y_k]\mathbb{E}[Y_l\right] \\ &&&= \sum_{r=1}^n \mathbb{E} \left [ Y_r^4 \right]+6\sum_{i\neq j} \mathbb{E} \left [ Y_i^2]\mathbb{E}[Y_j^2\right] \end{align*}
  3. Without loss of generality, we may assume they all have mean zero. Therefore we can consider the sitatuion as in the previous case with \(T\) and \(Y_i\)s. Note that \(\mathbb{E}(Y_i^4) = \sigma^4(\kappa + 3)\) and \(\textrm{Var}(T) = n \sigma^2\) \begin{align*} && \kappa_T &= \frac{\mathbb{E}(T^4)}{(\textrm{Var}(T))^2} - 3 \\ &&&= \frac{\sum_{r=1}^n \mathbb{E} \left [ Y_r^4 \right]+6\sum_{i\neq j} \mathbb{E} \left [ Y_i^2\right]\mathbb{E}\left[Y_j^2\right]}{n^2\sigma^4}-3 \\ &&&= \frac{n\sigma^4(\kappa+3)+6\binom{n}{2}\sigma^4}{n^2\sigma^4} -3\\ &&&= \frac{\kappa}{n} + \frac{3n + \frac{6n(n-1)}{2}}{n^2} - 3 \\ &&&= \frac{\kappa}{n} + \frac{3n^2}{n^2}-3 \\ &&&= \frac{\kappa}{n} \end{align*}

View
2015 Paper 1 Q8
D: 1484.0 B: 1516.0
proof by induction divisibility summation binomial theorem odd powers symmetric functions pairing argument

Show that:

  1. \(1+2+3+ \cdots + n = \frac12 n(n+1)\);
  2. if \(N\) is a positive integer, \(m\) is a non-negative integer and \(k\) is a positive odd integer, then \((N-m)^k +m^k\) is divisible by \(N\).
Let \(S = 1^k+2^k+3^k + \cdots + n^k\), where \(k\) is a positive odd integer. Show that if \(n\) is odd then \(S\) is divisible by \(n\) and that if \(n\) is even then \(S\) is divisible by \(\frac12 n\). Show further that \(S\) is divisible by \(1+2+3+\cdots +n\).

Solution:

  1. \(\,\) \begin{align*} && S & = 1 +\quad 2\quad \;\;+ \quad 3 \quad+ \cdots + \quad n \\ && S &= n + (n-1) + (n-2) + \cdots + 1 \\ && 2S &= (n+1) + (n+1) + \cdots + (n+1) \\ \Rightarrow && S &= \frac12n(n+1) \end{align*}
  2. \(\,\) \begin{align*} && (N-m)^{k} + m^k&= \sum_{i=0}^k \binom{k}{i} N^{k-i} (-m)^{i} + m^k \\ &&&= N\sum_{i=0}^{k-1} \binom{k}{i}N^{k-i-1}(-m)^i -m^k+m^k \\ &&&= N\sum_{i=0}^{k-1} \binom{k}{i}N^{k-i-1}(-m)^i \end{align*} which is clearly divisible by \(N\).
\begin{align*} 2S &= 2\sum_{i=1}^n i^k \\ &= \sum_{i=0}^n (\underbrace{(n-i)^k + i^k}_{\text{divisible by }n}) \\ \end{align*} Therefore \(2S\) is divisible by \(n\) and so if \(n\) is odd, \(n\) divides \(S\) and if \(n\) is even, \(\frac{n}{2}\) divides \(S\). Also notice \begin{align*} 2S &= 2\sum_{i=1}^n i^k \\ &= \sum_{i=1}^{n} (\underbrace{(n+1-i)^k + i^k}_{\text{divisible by }n+1}) \\ \end{align*} Therefore if \(n+1\) is odd, \(n+1 \mid S\) otherwise \(\frac{n+1}{2} \mid S\), and in either case \(\frac{n(n+1)}{2} \mid S\) (since they are both coprime) but this is the same as \(1 + 2 + \cdots + n \mid S\)

View
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
2015 Paper 2 Q3
D: 1600.0 B: 1483.4
combinatorics proof by induction triangles triangle inequality counting summation closed form formula

Three rods have lengths \(a\), \(b\) and \(c\), where \(a< b< c\). The three rods can be made into a triangle (possibly of zero area) if \(a+b\ge c\). Let \(T_{n}\) be the number of triangles that can be made with three rods chosen from \(n\) rods of lengths \(1\), \(2\), \(3\), \(\ldots\) , \(n\) (where \(n\ge3\)). Show that \(T_8-T_7 = 2+4+6\) and evaluate \(T_8 -T_6\). Write down expressions for \(T_{2m}-T_{2m-1}\) and \(T_{2m} - T_{2m-2}\). Prove by induction that \(T_{2m}=\frac 16 m (m-1)(4m+1)\,\), and find the corresponding result for an odd number of rods.

Solution: Every \(T_7\) triangle is valid, so we are interested in new triangles which have \(8\) has a longest side. We can have: \begin{array}{c|c|c} \text{longest} & \text{middle} & \text{shortest} \\ \hline 8 & 7 & 1-6 \\ 8 & 6 & 2-5 \\ 8 & 5 & 3-4 \end{array} which is \(6+4+2\) extra triangles. The new ones excluding all the sixes are: \begin{array}{c|c|c} \text{longest} & \text{middle} & \text{shortest} \\ \hline 8 & 7 & 1-6 \\ 8 & 6 & 2-5 \\ 8 & 5 & 3-4 \\ 7 & 6 & 1-5 \\ 7 & 5 & 2-4 \\ 7 & 4 & 3 \\ \end{array} Ie \(2+4+6 + 1 + 3+5\) \(T_{2m}-T_{2m-1} = 2 \frac{(m-1)m}{2} = m(m-1)\) and \(T_{2m}-T_{2m-2} = \frac{(2m-2)(2m-1)}{2}\) \(T_4 = 3\) (\(1,2,3\), \(1,3,4\), \(2,3,4\)) and \(\frac16 \cdot 2 \cdot 1 \cdot 9 = 3\) so the base case holds. Suppose it's true for some \(m = k\), then \begin{align*} && T_{2(k+1)} &= T_{2k} + \frac{2m(2m+1)}{2} \\ &&&= \frac{m(m-1)(4m+1)}{6} + \frac{6m(2m+1)}{6}\\ &&&= \frac{m(4m^2-3m-1+12m+6)}{6} \\ &&&= \frac{m(4m^2+9m+5)}{6}\\ &&&= \frac{m(4m+5)(m+1)}{6}\\ &&&= \frac{(m+1-1)(4(m+1)+5)(m+1)}{6}\\ \end{align*} as required, therefore it is true by induction. For odd numbers, we can see that \(T_{2m-1} = \frac{m(m-1)(4m+1)}{6} - m(m-1) = \frac{m(m-1)(4m-5)}{6}\)

View
2015 Paper 2 Q5
D: 1600.0 B: 1484.9
trigonometry arctan proof by induction telescoping summation tan addition formula right triangle infinite series

In this question, the \(\mathrm{arctan}\) function satisfies \(0\le \arctan x <\frac12 \pi\) for \(x\ge0\,\).

  1. Let \[ S_n= \sum_{m=1}^n \arctan \left(\frac1 {2m^2}\right) \,, \] for \(n=1, 2, 3, \ldots\) . Prove by induction that \[ \tan S_n = \frac n {n+1} \,. \] Prove also that \[ S_n = \arctan \frac n {n+1} \,. \]
  2. In a triangle \(ABC\), the lengths of the sides \(AB\) and \(BC\) are \(4n^2\) and \(4n^4-1\), respectively, and the angle at \(B\) is a right angle. Let \(\angle BCA = 2\alpha_n\). Show that \[ \sum_{n=1}^\infty \alpha_n = \tfrac14\pi \,. \]

Solution:

  1. Claim: \(\tan S_n = \frac n {n+1}\) Proof: (By Induction) Base case: (\(n=1\)): \begin{align*} && \tan \left ( \sum_{m=1}^1 \arctan \left ( \frac{1}{2m^2} \right) \right) &= \tan \left ( \arctan \left ( \frac{1}{2} \right) \right) \\ &&&= \frac12 = \frac{1}{1+1} \end{align*} Therefore the base case is true. Inductive step: Suppose our statement is true for some \(n = k\), ie \begin{align*} && \frac{k}{k+1} &= \tan \left ( \sum_{m=1}^k \arctan \left ( \frac{1}{2m^2} \right) \right) \\ \Rightarrow && \tan S_{k+1} &= \tan \left ( \sum_{m=1}^k \arctan \left ( \frac{1}{2m^2} \right) + \arctan \left ( \frac{1}{2 (k+1)^2} \right) \right) \\ &&&= \frac{\tan S_k + \tan \left ( \arctan \left ( \frac{1}{2 (k+1)^2} \right) \right)}{1-\tan S_k \tan \left ( \arctan \left ( \frac{1}{2 (k+1)^2} \right) \right)} \\ &&&= \frac{\frac{k}{k+1} + \frac{1}{2(k+1)^2}}{1-\frac{k}{k+1} \frac{1}{2(k+1)^2}} \\ &&&= \frac{2k(k+1)^2+(k+1)}{2(k+1)^3-k} \\ &&&= \frac{k+1}{(k+1)+1} \end{align*} Therefore it is true for \(n=k+1\). Conclusion: Therefore by the principle of mathematical induction since our statement is true for \(n=1\) and if it is true for \(n=k\) it is true for \(n=k+1\) it is true for all \(n\geq1\) Since \(S_n < \frac12 \pi\) for all \(n\), we must have \(\arctan \frac{n}{n+1} = S_n\)
  2. \(\tan (2\alpha_n) = \frac{4n^2}{4n^4-1} = \frac{2n^2+2n^2}{(2n^2)(2n^2)-1} = \frac{\frac{1}{2n^2}+\frac{1}{2n^2}}{1-\frac{1}{2n^2}\frac{1}{2n^2}} \Rightarrow \tan (\alpha_n) = \arctan \frac{1}{2n^2}\). In particular \(\displaystyle \sum_{n=1}^{N} \alpha_n = \arctan \frac{n}{n+1} \Rightarrow \sum_{n=1}^{\infty} \alpha_n \to \arctan 1 = \frac{\pi}{4} \)

View
2015 Paper 3 Q7
D: 1700.0 B: 1500.0
proof by induction differential operator polynomial binomial theorem divisibility combinatorial identity operator algebra summation

An operator \(\rm D\) is defined, for any function \(\f\), by \[ {\rm D}\f(x) = x\frac{\d\f(x)}{\d x} .\] The notation \({\rm D}^n\) means that \(\rm D\) is applied \(n\) times; for example \[ \displaystyle {\rm D}^2\f(x) = x\frac{\d\ }{\d x}\left( x\frac{\d\f(x)}{\d x} \right) \,. \] Show that, for any constant \(a\), \({\rm D}^2 x^a = a^2 x^a\,\).

  1. Show that if \(\P(x)\) is a polynomial of degree \(r\) (where \(r\ge1\)) then, for any positive integer \(n\), \({\rm D}^n\P(x)\) is also a polynomial of degree \(r\).
  2. Show that if \(n\) and \(m\) are positive integers with \(n < m\), then \({\rm D}^n(1-x)^m\) is divisible by \((1-x)^{m-n}\).
  3. Deduce that, if \(m\) and \(n\) are positive integers with \(n < m\), then \[ \sum_{r=0}^m (-1)^r \binom m r r^n =0 \, . \]
  4. [Not on original paper] Let \(\f_n(x) = D^n(1-x)^n\,\), where \(n\) is a positive integer. Prove that \(\f_n(1)=(-1)^nn!\, \).

Solution: \begin{align*} {\mathrm D}^2 x^a &= x\frac{\d\ }{\d x}\left( x\frac{\d}{\d x} \left ( x^a \right) \right) \\ &= x\frac{\d\ }{\d x}\left( ax^a \right) \\ &= a^2 x^a \end{align*}

  1. Claim: \({\mathrm D^n}(x^a) =a^n x^a\) Proof: Induct on \(n\). Base cases we have already seen, so consider \(D^{k+1}(x^a) = D(a^k x^a) = a^{k+1}x^a\) as required. Claim: \({\mathrm D}\) is linear, ie \({\mathrm D}(f(x) + g(x)) = {\mathrm D}(f(x)) + {\mathrm D}(g(x))\) Proof: \begin{align*} {\mathrm D}(f(x) + g(x)) &= x\frac{\d\ }{\d x}\left(f(x) + g(x) \right) \\ &= x\frac{\d\ }{\d x}f(x) + x\frac{\d\ }{\d x}g(x) \\ &= {\mathrm D}(f(x)) + {\mathrm D}(g(x)) \end{align*} Claim: If \(p(x)\) is a polynomial degree \(r\) then \({\mathrm D}^n p(x)\) is a polynomial degree \(n\). Proof: Since \({\mathrm D}\) is linear, it suffices to prove this for a monomial of degree \(n\), but this was already proven in the first question.
  2. Claim: If \(f(x)\) is some polynomial, \({\mathrm D}((1-x)^m f(x))\) is divisible by \((1-x)^{m-1}\) Proof: \({\mathrm D}((1-x)^mf(x)) = -xm(1-x)^{m-1}f(x) + (1-x)^mxf'(x) = x(1-x)^{m-1}((1-x)f'(x)-xf(x))\) as required. Therefore repeated application of \({\mathrm D}\) will reduce the factor of \(1-x\) by at most \(1\) each time as required.
  3. \begin{align*} {\mathrm D}^n(1-x)^m &= {\mathrm D}^n \left ( \sum_{r=0}^m \binom{m}{r}(-1)^r x^r\right) \\ &= \sum_{r=0}^m {\mathrm D}^n \left ( \binom{m}{r}(-1)^r x^r \right ) \\ &= \sum_{r=0}^m\binom{m}{r}(-1)^r r^n x^r \end{align*} Since the left-hand side is divisible by \(1-x\), if we substitute \(x = 1\), the sum must be \(0\), i.e., we get the desired result.
  4. On each application of \({\mathrm D}\) to \((1-x)^m f(x)\) we end up with a term in the form \(x(1-x)^{m-1}(x)\) and a term of the form \((1-x)^m\). After the latter term will be annihilated once we evaluate at \(x = 1\) because there will be insufficient applications to remove the factors of \(1-x\). Therefore we only need to focus on the term which does not get annihilated. This term is will be \((-x)^n n \cdot (n-1) \cdots 1\), so \(f_n(1) = (-1)^n n!\) as required. Alternatively: \begin{align*} {\mathrm D}^n((1-x)^n) &= D^{n-1}(-nx(1-x)^{n-1}) \\ &= -n{\mathrm D}^{n-1}(x(1-x)^{n-1}) \\ &= -n{\mathrm D}^{n-1}((x-1+1)(1-x)^{n-1}) \\ &= -n{\mathrm D}^{n-1}(-(1-x)^{n}+(1-x)^{n-1}) \\ &= -n{\mathrm D}^{n-1}(-(1-x)^{n})-n{\mathrm D}^{n-1}((1-x)^{n-1}) \\ \end{align*} Therefore, when this is evaluated at \(x = 1\), recursively, we will have \(f_n(1) = -nf_{n-1}(1)\), in particular, \(f_n(1) = (-1)^n n!\)

View