Problems

Filters
Clear Filters

22 problems found

2025 Paper 2 Q11
D: 1500.0 B: 1500.0
geometric distribution geometric series differentiation of series expected value binomial theorem combinatorics probability dice strictly increasing sequence approximation

  1. By considering the sum of a geometric series, or otherwise, show that \[\sum_{r=1}^{\infty} rx^{r-1} = \frac{1}{(1-x)^2} \quad \text{for } |x| < 1.\]
  2. Ali plays a game with a fair \(2k\)-sided die. He rolls the die until the first \(2k\) appears. Ali wins if all the numbers he rolls are even.
    1. Find the probability that Ali wins the game. If Ali wins the game, he earns £1 for each roll, including the final one. If he loses, he earns nothing.
    2. Find Ali's expected earnings from playing the game.
  3. Find a simplified expression for \[1 + 2\binom{n}{1}x + 3\binom{n}{2}x^2 + \ldots + (n+1)x^n,\] where \(n\) is a positive integer.
  4. Zen plays a different game with a fair \(2k\)-sided die. She rolls the die until the first \(2k\) appears, and wins if the numbers rolled are strictly increasing in size. For example, if \(k = 3\), she wins if she rolls 2, 6 or 1, 4, 5, 6, but not if she rolls 1, 4, 2, 6 or 1, 3, 3, 6. If Zen wins the game, she earns £1 for each roll, including the final one. If she loses, she earns nothing. Find Zen's expected earnings from playing the game.
  5. Using the approximation \[\left(1 + \frac{1}{n}\right)^n \approx e \quad \text{for large } n,\] show that, when \(k\) is large, Zen's expected earnings are a little over 35\% more than Ali's expected earnings.

Solution:

  1. Note that, \begin{align*} && \sum_{r = 0}^\infty x^r &= \frac{1}{1-x} && |x| < 1\\ \underbrace{\Rightarrow}_{\frac{\d}{\d x}} && \sum_{r = 0}^\infty rx^{r-1} &= \frac{1}{(1-x)^2} && |x| < 1\\ && \sum_{r = 1}^\infty rx^{r-1} &= \frac{1}{(1-x)^2} && |x| < 1\\ \end{align*}
    1. \begin{align*} && \mathbb{P}(\text{Ali wins in }s\text{ rounds}) &= \left ( \frac{k-1}{2k} \right)^{s-1} \frac{1}{2k} \\ \Rightarrow && \mathbb{P}(\text{Ali wins}) &= \sum_{s=1}^\infty \mathbb{P}(\text{Ali wins in }s\text{ rounds}) \\ &&&=\sum_{s=1}^\infty \left ( \frac{k-1}{2k} \right)^{s-1} \frac{1}{2k} \\ &&&= \frac{1}{2k} \sum_{s=0}^\infty \left ( \frac{k-1}{2k} \right)^{s} \\ &&&= \frac{1}{2k} \frac{1}{1 - \frac{k-1}{2k}} \\ &&&= \frac{1}{2k - (k-1)} \\ &&&= \frac{1}{k+1} \end{align*}
    2. \begin{align*} \mathbb{E}(\text{Ali score}) &= \sum_{s=1}^{\infty} s \mathbb{P}(\text{Ali wins in }s\text{ rounds}) \\ &= \sum_{s=1}^{\infty} s \left ( \frac{k-1}{2k} \right)^{s-1} \frac{1}{2k} \\ &= \frac{1}{2k} \frac{1}{\left (1 - \frac{k-1}{2k} \right)^2} \\ &= \frac{2k}{(k+1)^2} \end{align*}
  3. \begin{align*} && (1+x)^{n} &= \sum_{k=0}^n \binom{n}{k} x^k \\ \Rightarrow && x(1+x)^n &= \sum_{k=0}^n \binom{n}{k} x^{k+1} \\ \Rightarrow && (1+x)^n + nx(1+x)^{n-1} &= \sum_{k=0}^n (k+1)\binom{n}{k} x^k \\ \Rightarrow && (1+x)^{n-1}(1+(n+1)x) &= 1 + 2\binom{n}{1}x + 3\binom{n}{2}x^2 + \ldots + (n+1)x^n \end{align*}
  4. \begin{align*} \mathbb{E}(\text{Zen score}) &= \sum_{s=1}^{2k} s \mathbb{P} \left ( \text{Zen gets }s\text{ numbers in increasing order ending with }2k \right) \\ &= \sum_{s=1}^{2k} s \binom{2k-1}{s-1} \frac{1}{(2k)^s} \\ &= \frac{1}{2k}\sum_{s=0}^{2k-1} (s+1) \binom{2k-1}{s} \frac{1}{(2k)^s} \\ &= \frac{1}{2k} \left ( 1 + \frac{1}{2k} \right)^{2k-2} \left ( 1 + (2k-1+1) \frac{1}{2k} \right) \\ &= \frac{1}{k}\left ( 1 + \frac{1}{2k} \right)^{2k-2} \end{align*}
  5. Therefore as \(k \to \infty\) \begin{align*} \frac{\mathbb{E}(\text{Zen score})}{\mathbb{E}(\text{Ali score}) } &= \frac{1}{k}\left ( 1 + \frac{1}{2k} \right)^{2k-2} \big / \frac{2k}{(k+1)^2} \\ &= \frac{(k+1)^2}{2k^2} \cdot \left ( 1 + \frac{1}{2k} \right)^{2k} \cdot \left ( 1 + \frac{1}{2k} \right)^{-2} \\ &\to \frac12 e \approx 2.7/2 = 1.35 \end{align*} ie Zen's expected earnings are \(\approx 35\%\) more.

View
2024 Paper 3 Q11
D: 1500.0 B: 1500.0
binomial distribution binomial theorem expectation combinatorics optimisation symmetry argument binomial coefficient identity

In this question, you may use without proof the results \[\sum_{r=0}^{n} \binom{n}{r} = 2^n \quad \text{and} \quad \sum_{r=0}^{n} r\binom{n}{r} = n\,2^{n-1}.\]

  1. Show that \[r\binom{2n}{r} = (2n+1-r)\binom{2n}{2n+1-r}\] for \(1 \leqslant r \leqslant 2n\). Hence show that \[\sum_{r=0}^{2n} r\binom{2n}{r} = 2\sum_{r=n+1}^{2n} r\binom{2n}{r}.\]
  2. A fair coin is tossed \(2n\) times. The value of the random variable \(X\) is whichever is the larger of the number of heads and the number of tails shown. If \(n\) heads and \(n\) tails are shown, then \(X = n\). Show that \[\mathrm{E}(X) = n\left(1 + \frac{1}{2^{2n}}\binom{2n}{n}\right).\]
  3. Show that \(\dfrac{1}{2^{2n}}\dbinom{2n}{n}\) decreases as \(n\) increases.
  4. In a game, you choose a value of \(n\) and pay \(\pounds n\); then a fair coin is tossed \(2n\) times. You win an amount in pounds equal to the larger of the number of heads and the number of tails shown. If \(n\) heads and \(n\) tails are shown, then you win \(\pounds n\). How should you choose \(n\) to maximise your expected winnings per pound paid?

View
2023 Paper 2 Q6
D: 1500.0 B: 1500.0
proof by induction fibonacci sequence matrix exponentiation recurrence relation binomial theorem determinant 2x2 matrices

The sequence \(F_n\), for \(n = 0, 1, 2, \ldots\), is defined by \(F_0 = 0\), \(F_1 = 1\) and by \(F_{n+2} = F_{n+1} + F_n\) for \(n \geqslant 0\). Prove by induction that, for all positive integers \(n\), \[\begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix} = \mathbf{Q}^n,\] where the matrix \(\mathbf{Q}\) is given by \[\mathbf{Q} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}.\]

  1. By considering the matrix \(\mathbf{Q}^n\), show that \(F_{n+1}F_{n-1} - F_n^2 = (-1)^n\) for all positive integers \(n\).
  2. By considering the matrix \(\mathbf{Q}^{m+n}\), show that \(F_{m+n} = F_{m+1}F_n + F_m F_{n-1}\) for all positive integers \(m\) and \(n\).
  3. Show that \(\mathbf{Q}^2 = \mathbf{I} + \mathbf{Q}\). In the following parts, you may use without proof the Binomial Theorem for matrices: \[(\mathbf{I} + \mathbf{A})^n = \sum_{k=0}^{n} \binom{n}{k} \mathbf{A}^k.\]
    1. Show that, for all positive integers \(n\), \[F_{2n} = \sum_{k=0}^{n} \binom{n}{k} F_k\,.\]
    2. Show that, for all positive integers \(n\), \[F_{3n} = \sum_{k=0}^{n} \binom{n}{k} 2^k F_k\] and also that \[F_{3n} = \sum_{k=0}^{n} \binom{n}{k} F_{n+k}\,.\]
    3. Show that, for all positive integers \(n\), \[\sum_{k=0}^{n} (-1)^{n+k} \binom{n}{k} F_{n+k} = 0\,.\]

View
2023 Paper 3 Q4
D: 1500.0 B: 1500.0
binomial theorem trigonometric identities polynomial expansion chebyshev polynomials coefficient extraction combinatorics

Let \(n\) be a positive integer. The polynomial \(\mathrm{p}\) is defined by the identity \[\mathrm{p}(\cos\theta) \equiv \cos\big((2n+1)\theta\big) + 1\,.\]

  1. Show that \[\cos\big((2n+1)\theta\big) = \sum_{r=0}^{n} \binom{2n+1}{2r} \cos^{2n+1-2r}\theta\,(\cos^2\theta - 1)^r\,.\]
  2. By considering the expansion of \((1+t)^{2n+1}\) for suitable values of \(t\), show that the coefficient of \(x^{2n+1}\) in the polynomial \(\mathrm{p}(x)\) is \(2^{2n}\).
  3. Show that the coefficient of \(x^{2n-1}\) in the polynomial \(\mathrm{p}(x)\) is \(-(2n+1)2^{2n-2}\).
  4. It is given that there exists a polynomial \(\mathrm{q}\) such that \[\mathrm{p}(x) = (x+1)\,[\mathrm{q}(x)]^2\] and the coefficient of \(x^n\) in \(\mathrm{q}(x)\) is greater than \(0\). Write down the coefficient of \(x^n\) in the polynomial \(\mathrm{q}(x)\) and, for \(n \geqslant 2\), show that the coefficient of \(x^{n-2}\) in the polynomial \(\mathrm{q}(x)\) is \[2^{n-2}(1-n)\,.\]

View
2022 Paper 2 Q12
D: 1500.0 B: 1500.0
continuous probability distributions probability density function expectation median mode binomial theorem inequality

The random variable \(X\) has probability density function \[\mathrm{f}(x) = \begin{cases} kx^n(1-x) & 0 \leqslant x \leqslant 1\,,\\ 0 & \text{otherwise}\,,\end{cases}\] where \(n\) is an integer greater than 1.

  1. Show that \(k = (n+1)(n+2)\) and find \(\mu\), where \(\mu = \mathrm{E}(X)\).
  2. Show that \(\mu\) is less than the median of \(X\) if \[6 - \frac{8}{n+3} < \left(1 + \frac{2}{n+1}\right)^{n+1}.\] By considering the first four terms of the expansion of the right-hand side of this inequality, or otherwise, show that the median of \(X\) is greater than \(\mu\).
  3. You are given that, for positive \(x\), \(\left(1 + \dfrac{1}{x}\right)^{x+1}\) is a decreasing function of \(x\). Show that the mode of \(X\) is greater than its median.

Solution:

  1. \(\,\) \begin{align*} && 1 &= \int_0^1 kx^n(1-x) \d x \\ &&&= k\left [\frac{x^{n+1}}{n+1} - \frac{x^{n+2}}{n+2} \right]_0^1 \\ &&&= \frac{k}{(n+1)(n+2)} \\ \Rightarrow && k &= (n+1)(n+2) \\ \\ && \E[X] &= \int_0^1 kx^{n+1}(1-x) \d x \\ &&&= k\left [ \frac{x^{n+2}}{n+2} - \frac{x^{n+3}}{n+3} \right]_0^1 \\ &&&= \frac{(n+1)(n+2)}{(n+2)(n+3)} \\ &&&= \frac{n+1}{n+3} \end{align*}
  2. If \(\mu\) is less than the median then \begin{align*} && \frac12 &> \int_0^{\mu} kx^{n}(1-x) \d x \\ &&&= \left [k \frac{x^{n+1}}{n+1} - \frac{x^{n+2}}{n+2} \right]_0^\mu \\ &&&= \mu^{n+1}\left ((n+2) - (n+1) \frac{n+1}{n+3} \right) \\ \Rightarrow && \left ( 1 + \frac{2}{n+1} \right)^{n+1} &> 2 \frac{(n+2)(n+3) - (n+1)^2}{n+3} \\ &&&= \frac{6n+10}{n+3} = 6 - \frac{8}{n+3} \end{align*} \begin{align*} && \left ( 1 + \frac{2}{n+1} \right)^{n+1} &= 1 + (n+1) \frac{2}{n+1} + \frac{(n+1)n}{2} \frac{4}{(n+1)^2} + \frac{(n+1)n(n-1)}{6} \frac{8}{(n+1)^3} + \cdots \\ &&&= 1 + 2 + \frac{2n}{n+1} + \frac{4n(n-1)}{3(n+1)^2} + \cdots \\ &&&= 5 - \frac{2}{n+1} + \frac{4((n+1)^2-3(n+1)+3)}{3(n+1)^2} \\ &&&= 6 + \frac13 - \frac{6}{n+1} - \frac{4}{3(n+1)^2} \\ &&&> 6 - \frac{8}{n+3} \end{align*} as required.
  3. To find the mode, we need to find the maximum of \(x^n(1-x)\) which occurs when \(nx^{n-1}(1-x) - x^n = x^{n-1}(n-(n+1)x)\) ie where \(x = \frac{n}{n+1}\), therefore we need to look at: \begin{align*} && \mathbb{P}(X \leq \tfrac{n}{n+1}) &= \int_0^{n/(n+1)} k x^n(1-x) \d x \\ &&&= \frac{n^{n+1}}{(n+1)^{n+1}} \left ( (n+2) - (n+1) \frac{n}{n+1} \right) \\ &&&= 2\frac{n^{n+1}}{(n+1)^{n+1}} \\ &&&= 2 \left ( \frac{1}{1+\frac1n} \right)^{n+1} \\ &&&\geq 2 \frac{1}{(1 + \frac11)^2} = \frac12 \end{align*} as required

View
2022 Paper 3 Q8
D: 1500.0 B: 1500.0
de moivre's theorem complex numbers binomial theorem trigonometric identities proof by contradiction irrationality number theory

  1. Use De Moivre's theorem to prove that for any positive integer \(k > 1\), \[ \sin(k\theta) = \sin\theta\cos^{k-1}\theta \left( k - \binom{k}{3}(\sec^2\theta - 1) + \binom{k}{5}(\sec^2\theta - 1)^2 - \cdots \right) \] and find a similar expression for \(\cos(k\theta)\).
  2. Let \(\theta = \cos^{-1}(\frac{1}{a})\), where \(\theta\) is measured in degrees, and \(a\) is an odd integer greater than \(1\). Suppose that there is a positive integer \(k\) such that \(\sin(k\theta) = 0\) and \(\sin(m\theta) \neq 0\) for all integers \(m\) with \(0 < m < k\). Show that it would be necessary to have \(k\) even and \(\cos(\frac{1}{2}k\theta) = 0\). Deduce that \(\theta\) is irrational.
  3. Show that if \(\phi = \cot^{-1}(\frac{1}{b})\), where \(\phi\) is measured in degrees, and \(b\) is an even integer greater than \(1\), then \(\phi\) is irrational.

View
2016 Paper 3 Q5
D: 1700.0 B: 1500.0
binomial theorem proof by induction prime numbers inequality divisibility binomial coefficient number theory

  1. By considering the binomial expansion of \((1+x)^{2m+1}\), prove that \[ \binom{ 2m \! +\! 1}{ m} < 2^{2m}\,, \] for any positive integer \(m\).
  2. For any positive integers \(r\) and \(s\) with \(r< s\), \(P_{r,s}\) is defined as follows: \(P_{r,s}\) is the product of all the prime numbers greater than \(r\) and less than or equal to \(s\), if there are any such primes numbers; if there are no such primes numbers, then \(P_{r,s}=1\,\). For example, \(P_{3,7}=35\), \(P_{7,10}=1\) and \(P_{14,18}=17\). Show that, for any positive integer \(m\), \(P_{m+1\,,\, 2m+1} \) divides \(\displaystyle \binom{ 2m \! +\! 1}{ m} \,,\) and deduce that \[ P_{m+1\,,\, 2m+1} < 2^{2m} \,. \]
  3. Show that, if \(P_{1,k} < 4^k\) for \(k = 2\), \(3\), \(\ldots\), \(2m\), then \( P_{1,2m+1} < 4^{2m+1}\,\).
  4. Prove that \(\P_{1,n} < 4^n\) for \(n\ge2\).

Solution:

  1. Notice that \((1+x)^{2m+1} = 1+\binom{2m+1}{1}x+\cdots + \binom{2m+1}{m}x^{m} + \binom{2m+1}{m+1} + \cdots\). Notice also that \(\binom{2m+1}{m} = \binom{2m+1}{m+1}\). Therefore evaluating at \(x = 1\), we see \(2^{2m+1} > \binom{2m+1}{m} + \binom{2m+1}{m+1} = 2 \binom{2m+1}{m} \Rightarrow \binom{2m+1}{m} < 2^{2m}\)
  2. Each prime dividing \(P_{m+1, 2m+1}\) divides the numerator of \(\binom{2m+1}{m}\) since it appears in \((2m+1)!\), but not the denominator, since they wont appear in \(m!\) or \((m+1)!\), and since they are prime they have to appear to divide it. Therefore the must divide \(\binom{2m+1}{m}\) and therefore \(P_{m+1,2m+1}\) must divide that binomail coefficient. Since \(a \mid b \Rightarrow a \leq b\) we must have \(P_{m+1, 2m+1} \leq \binom{2m+1}{m} < 2^{2m}\)
  3. Since \begin{align*} P_{1,2m+1} &= P_{1,m+1}P_{m+1, 2m+1} \tag{split into primes below \(m+1\) and abvoe} \\ &< 4^{m+1}P_{m+1,2m+1} \tag{use the condition from the question}\\ &<4^{m+1}2^{2m} \tag{use our inequality} \\ &= 4^{2m+1} \end{align*}
  4. We proceed by (strong) induction. Base case: (\(n = 2\)): \(P_{1,2} = 2 < 4^2 =16\) Suppose it is true for all \(k=2,3,\cdots,2m\) then it is true for \(k=2m+1\) by the previous part of the question. However it is also true for \(k=2m+2\), since that can never be prime (as n is now an even number bigger than 2). Therefore by the principle of mathematical induction it is true for all \(n\).

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 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
2014 Paper 2 Q8
D: 1600.0 B: 1486.3
binomial theorem binomial coefficients optimisation inequality integer constraints maximisation positive integer n

For positive integers \(n\), \(a\) and \(b\), the integer \(c_r\) (\(0\le r\le n\)) is defined to be the coefficient of \(x^r\) in the expansion in powers of \(x\) of \((a+bx)^n\). Write down an expression for \(c_r\) in terms of \(r\), \(n\), \(a\) and \(b\). For given \(n\), \(a\) and \(b\), let \(m\) denote a value of \(r\) for which \(c_r\) is greatest (that is, \(c_m \ge c_r\) for \(0\le r\le n\)). Show that \[ \frac{b(n+1)}{a+b} - 1 \le m \le \frac {b(n+1)}{a+b} \,. \] Deduce that \(m\) is either a unique integer or one of two consecutive integers. Let \(G(n,a,b)\) denote the unique value of \(m\) (if there is one) or the larger of the two possible values of \(m\).

  1. Evaluate \(G(9,1,3)\) and \(G(9,2,3)\).
  2. For any positive integer \(k\), find \(G(2k,a,a)\) and \(G(2k-1,a,a)\) in terms of \(k\).
  3. For fixed \(n\) and \(b\), determine a value of \(a\) for which \(G(n,a,b)\) is greatest.
  4. For fixed \(n\), find the greatest possible value of \(G(n,1,b)\). For which values of \(b\) is this greatest value achieved?

Solution: \(c_r = \binom{n}{r}a^{n-r}b^r\) \begin{align*} && c_m &\geq c_{m+1} \\ \Rightarrow && \binom{n}{m} a^{n-m}b^m &\geq \binom{n}{m+1} a^{n-m-1}b^{m+1} \\ \Rightarrow && \frac{1}{(n-m)}a &\geq \frac{1}{m+1}b \\ \Rightarrow && (m+1)a &\geq (n-m)b \\ \Rightarrow && m(a+b) &\geq nb -a \\ \Rightarrow && m &\geq \frac{n(b+1)-a-b}{a+b}=\frac{n(b+1)}{a+b} - 1 \\ \\ && c_m &\geq c_{m-1} \\ \Rightarrow && \binom{n}{m} a^{n-m}b^m &\geq \binom{n}{m-1} a^{n-m+1}b^{m-1} \\ \Rightarrow && \frac{1}m b &\geq \frac{a}{(n-m+1)} \\ \Rightarrow && (n-m+1)b &\geq ma \\ \Rightarrow && (n+1)b &\geq m(a+b) \\ \Rightarrow && m &\leq \frac{(n+1)b}{a+b} \end{align*} Since \(m\) lies between two values \(1\) apart is is either equal to one of those two values or is the unique integer between them. Let \(\displaystyle G(n,a,b) = \left \lfloor \frac{b(n+1)}{a+b} \right \rfloor\), so

  1. \(\,\) \begin{align*} && G(9,1,3) &= \left \lfloor \frac{3(9+1)}{1+3} \right \rfloor \\ &&&= \left \lfloor \frac{30}{4} \right \rfloor \\ &&&= 7 \\ \\ && G(9,2,3) &= \left \lfloor \frac{3(9+1)}{2+3} \right \rfloor \\ &&&= \left \lfloor \frac{30}{5} \right \rfloor \\ &&&= 6 \end{align*}
  2. \(\,\) \begin{align*} && G(2k, a, a) &= \left \lfloor \frac{a(2k+1)}{a+a} \right \rfloor \\ && &= \left \lfloor \frac{2k+1}{2} \right \rfloor \\ &&&= k \\ \\ && G(2k-1, a, a) &= \left \lfloor \frac{a(2k-1+1)}{a+a} \right \rfloor \\ && &= \left \lfloor k\right \rfloor \\ &&&= k \\ \end{align*}
  3. \(G(n,a,b)\) is decreasing in \(a\), therefore take \(a = 1\).
  4. For fixed \(n\), we are looking at \(\frac{a(n+1)}{a+b}\) and we want this to be as large as possible. By considering \((n+1) - \frac{b(n+1)}{a+b}\) we can see this is increasing in \(b\) and the largest value possible is \(n\). This is achieved when \begin{align*} && \frac{b(n+1)}{a+b} & \geq n \\ \Leftrightarrow && bn + b &\geq na + bn \\ \Leftrightarrow && b& \geq na \end{align*}

View
2013 Paper 1 Q6
D: 1500.0 B: 1501.4
binomial theorem binomial coefficients Pascals identity Fibonacci sequence recurrence relation summation proof by algebraic manipulation combinatorial identity

By considering the coefficient of \(x^r\) in the series for \((1+x)(1+x)^n\), or otherwise, obtain the following relation between binomial coefficients: \[ \binom n r + \binom n {r-1} = \binom {n+1} r \qquad (1\le r\le n). \] The sequence of numbers \(B_0\), \(B_1\), \(B_2\), \(\ldots\) is defined by \[ B_{2m} = \sum_{j=0}^m \binom{2m-j}j \text{ and } B_{2m+1} = \sum_{k=0}^m \binom{2m+1-k}k . \] Show that \(B_{n+2} - B_{n+1} = B_{n}\,\) (\(n=0\), \(1\), \(2\), \(\ldots\,\)). What is the relation between the sequence \(B_0\), \(B_1\), \(B_2\), \(\ldots\) and the Fibonacci sequence \(F_0\), \(F_1\), \(F_2\), \(\ldots\) defined by \(F_0=0\), \(F_1=1\) and \(F_n = F_{n-1}+F_{n-2}\) for \(n\ge2\)?

Solution: The coefficient of \(x^{r-1}\) in \((1+x)^n\) is \(\binom{n}{r-1}\) and the coefficient of \(x^r\) in \((1+x)^n\) is \(\binom{n}{r}\). The only ways to get \(x^r\) in the expansion of \((1+x)(1+x)^n\) is to either multiply the \(x^r\) term from the second expansion by \(1\) or the \(x^{r-1}\) term by \(x\). This is \(\binom{n}{r-1} + \binom{n}{r}\). However, the coefficient of \(x^r\) in \((1+x)^{n+1}\) is \(\binom{n+1}r\), so \(\binom{n}{r} + \binom{n}{n-1} = \binom{n+1}r\). Claim: \(B_{n+2} - B_{n+1} = B_{n}\). Proof: Consider \(n\) even, ie \(n = 2m\) \begin{align*} B_{n+2} - B_{n+1} &= \sum_{j=0}^{m+1} \binom{2(m+1)-j}{j} - \sum_{j=0}^m \binom{2m+1-j}{j} \\ &= \binom{2(m+1)-(m+1)}{m+1} +\sum_{j=0}^m \left ( \binom{2(m+1)-j}{j} - \binom{2m+1-j}{j} \right) \\ &= 1 + \sum_{j=1}^m \binom{2m+1-j}{j-1} \\ &= 1 + \sum_{j=0}^{m-1} \binom{2m-j}{j} \\ &= \binom{m}{m} + \sum_{j=0}^{m-1} \binom{2m-j}{j} \\ &= \sum_{j=0}^{m} \binom{2m-j}{j} \\ &= B_n \end{align*} Consider \(n\) even, ie \(n = 2m+1\) \begin{align*} B_{n+2} - B_{n+1} &= \sum_{j=0}^{m+1} \binom{2(m+1)+1-j}{j} - \sum_{j=0}^{m+1} \binom{2(m+1)-j}{j} \\ &= \sum_{j=0}^{m+1} \left (\binom{2(m+1)+1-j}{j} - \binom{2(m+1)-j}{j}\right)\\ &= \sum_{j=1}^{m+1} \binom{2(m+1)-j}{j-1} \\ &= \sum_{j=0}^{m} \binom{2m+1-j}{j} \\ &= B_n \end{align*} as required. \(B_0 = 1, B_1 = 2\), therefore \(B_n = F_{n+2}\)

View
2010 Paper 1 Q5
D: 1484.0 B: 1484.0
binomial theorem binomial coefficients summation identity substitution differentiation integration polynomial identity

By considering the expansion of \(\left(1+x\right)^{n}\) where \(n\) is a positive integer, or otherwise, show that:

  1. \[\binom{n}{0}+\binom{n}1+\binom{n}2 +\cdots +\binom{n}n=2^{n} \]
  2. \[\binom{n}{1}+2\binom{n}2+3\binom{n}3 +\cdots +n\binom{n}n=n2^{n-1} \]
  3. \[\binom{n}{0}+\frac12\binom{n}1+\frac13\binom{n}2 +\cdots +\frac1{n+1}\binom{n}n=\frac1{n+1}(2^{n+1}-1) \]
  4. \[\binom{n}{1}+2^2\binom{n}2+3^2\binom{n}3 +\cdots +n^2\binom{n}n=n(n+1)2^{n-2} \]

Solution:

  1. Notice that \begin{align*} && (1+x)^n &= \sum_{i=0}^n \binom{n}{i} x^i \\ \text{Evaluate at }x = 1: && 2^n &= \sum_{i=0}^n \binom{n}{i} \end{align*}
  2. \(\,\) \begin{align*} && (1+x)^n &= \sum_{i=0}^n \binom{n}{i} x^i \\ \frac{\d}{\d x}: && n(1+x)^{n-1} &= \sum_{i=1}^n i\binom{n}{i} x^{i-1} \\ \text{Evaluate at }x = 1: && n2^{n-1} &= \sum_{i=1}^n i\binom{n}{i} \end{align*}
  3. \(\,\) \begin{align*} && (1+x)^n &= \sum_{i=0}^n \binom{n}{i} x^i \\ \Rightarrow && \int_0^1(1+x)^n \d x &= \int_0^1 \sum_{i=0}^n \binom{n}{i} x^i \d x \\ \Rightarrow && \frac{1}{n+1}(2^{n+1}-1) &= \sum_{i=0}^n \binom{n}{i}\int_0^1 x^i \d x\\ &&& = \sum_{i=0}^n \frac{1}{i+1}\binom{n}{i} \\ \end{align*}
  4. \(\,\) \begin{align*} && (1+x)^n &= \sum_{i=0}^n \binom{n}{i} x^i \\ \frac{\d}{\d x}: && n(1+x)^{n-1} &= \sum_{i=1}^n i\binom{n}{i} x^{i-1} \\ \times x: && nx(1+x)^{n-1} &= \sum_{i=1}^n i\binom{n}{i} x^{i} \\ \frac{\d}{\d x}: && n(1+x)^{n-1}+n(n-1)x(1+x)^{n-2} &= \sum_{i=1}^n i^2\binom{n}{i} x^{i-1} \\ \text{Evaluate at }x = 1: && \sum_{i=1}^n i^2\binom{n}{i} &= n(1+1)^{n-1}+n(n-1)x(1+1)^{n-2} \\ &&&= 2^{n-2} \left (n(n-1) + 2n \right) \\ &&&= n(n+1)2^{n-2} \end{align*}

View
2008 Paper 3 Q2
D: 1700.0 B: 1555.2
sequences summation binomial theorem recurrence relation proof by induction polynomial power sums

Let \(S_k(n) \equiv \sum\limits_{r=0}^n r^k\,\), where \(k\) is a positive integer, so that \[ S_1(n) \equiv \tfrac12 n(n+1) \text{ and } S_2(n) \equiv \tfrac16 n(n+1)(2n+1)\,. \]

  1. By considering \(\sum\limits_{r=0}^n \left[ (r+1)^k-r^k\right]\, \), show that \[ kS_{k-1}(n)=(n+1)^k -(n+1) - \binom{k}{2} S_{k-2}(n) - \binom {k}{3} S_{k-3}(n) - \cdots - \binom{k}{k-1} S_{1}(n) \;. \tag{\(*\)} \] Obtain simplified expressions for \(S_3(n)\) and \(S_4(n)\).
  2. Explain, using \((*)\), why \(S_k(n)\) is a polynomial of degree \(k+1\) in \(n\). Show that in this polynomial the constant term is zero and the sum of the coefficients is 1.

Solution:

  1. \begin{align*} &&(n+1)^k &= \sum_{r=0}^n \left [ (r+1)^k - r^k \right] \\ &&&= \sum_{r=0}^n \left [ \left ( \binom{k}{0}r^k+\binom{k}1r^{k-1} + \binom{k}{2}r^{k-2} + \cdots + \binom{k}{k} 1 \right) - r^k\right] \\ &&&= \sum_{r=0}^n \left ( \binom{k}1r^{k-1} + \binom{k}{2}r^{k-2} + \cdots + \binom{k}{k} 1 \right) \\ &&&=k \sum_{r=0}^n r^{k-1} + \binom{k}{2}\sum_{r=0}^nr^{k-2} + \cdots + \binom{k}{k} \sum_{r=0}^n 1 \\ &&&= kS_{k-1}(n) + \binom{k}2 S_{k-2}(n) + \cdots +\binom{k}{k-1}S_1(n) + (n+1) \\ \Rightarrow && k S_{k-1}(n) &= (n+1)^k -(n+1) -\binom{k}2 S_{k-2}(n) - \cdots -\binom{k}{k-1}S_1(n) \\ && 4S_3(n) &= (n+1)^4-(n+1) - \binom{4}{2} \frac{n(n+1)(2n+1)}{6} - \binom{4}{3} \frac{n(n+1)}{2} \\ &&&= (n+1) \left ( (n+1)^3-1 - n(2n+1)-2n \right) \\ &&&= (n+1) \left ( n^3+3n^2+3n+1-1 - 2n^2-3n \right) \\ &&&= (n+1) \left ( n^3+n^2 \right) \\ &&&= n^2(n+1)^2 \\ \Rightarrow && S_3(n) &= \frac{n^2(n+1)^2}{4} \\ \\ &&5S_4(n) &=(n+1)^5-(n+1) - \binom{5}{2} \frac{n^2(n+1)^2}4 - \binom{5}{3} \frac{n(n+1)(2n+1)}{6} - \binom{5}{4} \frac{n(n+1)}{2} \\ &&&= (n+1) \left ((n+1)^4 - 1-\frac{5n^2(n+1)}{2} - \frac{5n(2n+1)}{3} -\frac{5n}{2}\right)\\ &&&= \frac{n+1}{6} \left (6(n+1)^4-6-15n^2(n+1)-10n(2n+1)-15n \right) \\ &&&= \frac{n+1}{6} \left (6n^4+24n^3+36n^2+24n+6 -6-15n^3-15n^2-20n^2-10n-15n\right) \\ &&&= \frac{n+1}{6} \left (6n^4+9n^3+n^2-n\right) \\ &&&= \frac{(n+1)n(2n+1)(3n^2+3n-1)}{6} \\ \Rightarrow && S_4(n) &= \frac{(n+1)n(2n+1)(3n^2+3n-1)}{30} \end{align*}
  2. Proceeding by induction, since \(S_k(n)\) is a polynomial of degree \(k+1\) for small \(k\), we can see that \[ (k+1)S_k(n) = \underbrace{(n+1)^{k+1}}_{\text{poly deg }=k+1} - \underbrace{(n+1)}_{\text{poly deg}=1} - \underbrace{\binom{k+1}{2}S_{k-1}(n)}_{\text{poly deg}=k} - \underbrace{\cdots}_{\text{polys deg}< k} - \underbrace{\binom{k+1}{k} S_1(n)}_{\text{poly deg}=1}\] therefore \(S_k(n)\) is a polynomial of degree \(k+1\) (in fact with leading coefficient \(\frac{1}{k+1}\). Since \(S_k(0) = \sum_{r=0}^{0} r^k = 0\) there is no constant term, and since \(S_k(1) = \sum_{r=0}^1 r^k = 1\) the sum of the coefficients is \(1\)

View
2000 Paper 1 Q2
D: 1516.0 B: 1499.4
binomial theorem binomial expansion coefficient extraction negative powers algebraic manipulation factorisation

Show that the coefficient of \(x^{-12}\) in the expansion of \[ \left(x^{4}-\frac{1}{x^{2}}\right)^{5} \left(x-\frac{1}{x}\right)^{6} \] is \(-15\), and calculate the coefficient of \(x^2\). Hence, or otherwise, calculate the coefficients of \(x^4\) and \(x^{38}\) in the expansion of \[ (x^2-1)^{11}(x^4+x^2+1)^5. \]

Solution: The powers of \(x\) in the first bracket will be \(x^{20}, x^{14}, \cdots, x^{-10}\). The powers of \(x\) in the second bracket will be \(x^6, x^4, \cdots, x^{-6}\). Therefore we can achieve \(x^{-12}\) in only one way: \begin{array}{c|c|c|c|c} 1\text{st bracket} & 2\text{nd bracket} & 1\text{st coef} & 2\text{nd coef} & \text{prod} \\ \hline x^{-10} & x^{-2} & \binom{5}{5}(-1)^5 = -1 & \binom{6}{4}(-1)^4 = 15& -15 \\ \end{array} We can achieve \(x^2\) as follows: \begin{array}{c|c|c|c|c} 1\text{st bracket} & 2\text{nd bracket} & 1\text{st coef} & 2\text{nd coef} & \text{prod} \\ \hline x^{-4} & x^{6} & \binom{5}{4}(-1)^4 = 5 & \binom{6}{0}(-1)^0 = 1& 5 \\ x^{2} & x^{0} & \binom{5}{3}(-1)^3 = -10 & \binom{6}{3}(-1)^3 = -20 & 200 \\ x^{8} & x^{-6} & \binom{5}{2}(-1)^2 = 10 & \binom{6}{6}(-1)^6 = 1 & 10 \end{array} Therefore the coefficient is \(215\) \((x^2-1)(x^4+x^2+1) = x^6-1\), therefore \begin{align*} (x^2-1)^{11}(x^4+x^2+1)^5 &= (x^2-1)^6(x^6-1)^5 \\ &= x^6\left(x-\frac1x\right)^6(x^6-1)^6 \\ &= x^6\left(x-\frac1x\right)^6\left(x^2\left(x^4-\frac{1}{x^2}\right)\right)^5 \\ &= x^6\left(x-\frac1x\right)^6x^{10}\left(x^4-\frac{1}{x^2}\right)^5 \\ &= x^{16}\left(x-\frac1x\right)^6\left(x^4-\frac{1}{x^2}\right)^6 \\ \end{align*} Therefore the coefficient of \(x^4\) is the coefficient of \(x^{4-16} = x^{-12}\) in our original expression, ie \(-15\). Similarly, the coefficient of \(x^{38}\) is the coefficient of \(x^{38-16} = x^{22}\), which can only be achieved in one way: \begin{array}{c|c|c|c|c} 1\text{st bracket} & 2\text{nd bracket} & 1\text{st coef} & 2\text{nd coef} & \text{prod} \\ \hline x^{20} & x^{2} & \binom{5}{0}(-1)^0 = 1 & \binom{6}{2}(-1)^2 = 15& 15 \\ \end{array} Therefore the coefficient is \(15\)

View
2000 Paper 3 Q7
D: 1700.0 B: 1516.0
sequences convergence binomial theorem AM-GM inequality infinite product exponential function factorial inequality

Given that $$\e = 1 + {1 \over 1 !} + {1 \over 2 !} + {1 \over 3 !} + \cdots + {1 \over r !} + \cdots \; ,$$ use the binomial theorem to show that $$ {\left( 1 + {1 \over n} \right)}^{\!n} < \e $$ for any positive integer \(n\). The product \({\rm P }( n )\) is defined, for any positive integer \(n\), by $$ {\rm P} ( n ) = {3 \over 2} \cdot {5 \over 4} \cdot {9 \over 8} \cdot \ldots \cdot {2^n + 1 \over 2^n} . $$ Use the arithmetic-geometric mean inequality, $$ {a_1 + a_2 + \cdots + a_n \over n} \ge \ {\left( a_1 \cdot a_2 \cdot \ldots \cdot a_n \right)}^{1 \over n}\,, $$ to show that \({\rm P }( n ) < \e\) for all \(n\) . Explain briefly why \({\rm P} ( n )\) tends to a limit as \(n\to\infty\). Show that this limit, \(L\), satisfies \(2 < L\le\e\).

View