Problems

Filters
Clear Filters

10 problems found

2022 Paper 3 Q11
D: 1500.0 B: 1500.0
binomial distribution mean deviation binomial coefficient combinatorial identity expected value symmetry fair coin

A fair coin is tossed \(N\) times and the random variable \(X\) records the number of heads. The mean deviation, \(\delta\), of \(X\) is defined by \[ \delta = \mathrm{E}\big(|X - \mu|\big) \] where \(\mu\) is the mean of \(X\).

  1. Let \(N = 2n\) where \(n\) is a positive integer.
    1. Show that \(\mathrm{P}(X \leqslant n-1) = \frac{1}{2}\big(1 - \mathrm{P}(X=n)\big)\).
    2. Show that \[ \delta = \sum_{r=0}^{n-1}(n-r)\binom{2n}{r}\frac{1}{2^{2n-1}}\,. \]
    3. Show that for \(r > 0\), \[ r\binom{2n}{r} = 2n\binom{2n-1}{r-1}\,. \] Hence show that \[ \delta = \frac{n}{2^{2n}}\binom{2n}{n}\,. \]
  2. Find a similar expression for \(\delta\) in the case \(N = 2n+1\).

Solution:

  1. When \(N = 2n+1\), \(\mu = n +\frac12\) and so \begin{align*} && \delta &= \E[|X-\mu|] \\ &&&= \sum_{i=0}^n (n + \tfrac12 - i) \frac{1}{2^{2n+1}} \binom{2n+1}{i} + \sum_{i=n+1}^{2n+1} (i-n - \tfrac12) \frac{1}{2^{2n+1}} \binom{2n+1}{i} \\ &&&= 2\sum_{i=0}^n (n + \tfrac12 - i) \frac{1}{2^{2n+1}} \binom{2n+1}{i} \\ &&&= \frac{(2n +1)}{2^{2n+1}}\sum_{i=0}^n \binom{2n+1}i - \frac{2}{2^{2n+1}}\sum_{i=0}^n i \binom{2n+1}{i} \\ &&&= \frac{(2n +1)}{2^{2n+1}}\sum_{i=0}^n \binom{2n+1}i - \frac{2}{2^{2n+1}}\sum_{i=1}^n (2n+1) \binom{2n}{i-1} \\ &&&= \frac{(2n +1)}{2^{2n+1}}2^{2n} - \frac{2(2n+1)}{2^{2n+1}}\sum_{i=0}^{n-1} \binom{2n}{i} \\ &&&= \frac{(2n +1)}{2} - \frac{2(2n+1)}{2^{2n+1}} \frac12\left (2^{2n} - \binom{2n}{n} \right) \\ &&&= \frac{2n+1}{2^{2n+1}}\binom{2n}{n} \end{align*}

View
2018 Paper 3 Q12
D: 1700.0 B: 1516.0
probability order statistics uniform distribution binomial coefficients probability density function integration expectation combinatorial identity Beta function

A random process generates, independently, \(n\) numbers each of which is drawn from a uniform (rectangular) distribution on the interval 0 to 1. The random variable \(Y_k\) is defined to be the \(k\)th smallest number (so there are \(k-1\) smaller numbers).

  1. Show that, for \(0\le y\le1\,\), \[ {\rm P}\big(Y_k\le y) =\sum^{n}_{m=k}\binom{n}{m}y^{m}\left(1-y\right)^{n-m} . \tag{\(*\)} \]
  2. Show that \[ m\binom n m = n \binom {n-1}{m-1} \] and obtain a similar expression for \(\displaystyle (n-m) \, \binom n m\,\). Starting from \((*)\), show that the probability density function of \(Y_k\) is \[ n\binom{ n-1}{k-1} y^{k-1}\left(1-y\right)^{ n-k} \,.\] Deduce an expression for \(\displaystyle \int_0^1 y^{k-1}(1-y)^{n-k} \, \d y \,\).
  3. Find \(\E(Y_k) \) in terms of \(n\) and \(k\).

Solution:

  1. \begin{align*} && \mathbb{P}(Y_k \leq y) &= \sum_{j=k}^n\mathbb{P}(\text{exactly }j \text{ values less than }y) \\ &&&= \sum_{j=k}^m \binom{m}{j} y^j(1-y)^{n-j} \end{align*}
  2. This is the number of ways to choose a committee of \(m\) people with the chair from those \(m\) people. This can be done in two ways. First: choose the committee in \(\binom{n}{m}\) ways and choose the chair in \(m\) ways so \(m \binom{n}{m}\). Alternatively, choose the chain in \(n\) ways and choose the remaining \(m-1\) committee members in \(\binom{n-1}{m-1}\) ways. Therefore \(m \binom{n}{m} = n \binom{n-1}{m-1}\) \begin{align*} (n-m) \binom{n}{m} &= (n-m) \binom{n}{n-m} \\ &= n \binom{n-1}{n-m-1} \\ &= n \binom{n-1}{m} \end{align*} \begin{align*} f_{Y_k}(y) &= \frac{\d }{\d y} \l \sum^{n}_{m=k}\binom{n}{m}y^{m}\left(1-y\right)^{n-m} \r \\ &= \sum^{n}_{m=k} \l \binom{n}{m}my^{m-1}\left(1-y\right)^{n-m} -\binom{n}{m}(n-m)y^{m}\left(1-y\right)^{n-m-1} \r \\ &= \sum^{n}_{m=k} \l n \binom{n-1}{m-1}y^{m-1}\left(1-y\right)^{n-m} -n \binom{n-1}{m} y^{m}\left(1-y\right)^{n-m-1} \r \\ &= n\sum^{n}_{m=k} \binom{n-1}{m-1}y^{m-1}\left(1-y\right)^{n-m} -n\sum^{n+1}_{m=k+1} \binom{n-1}{m-1} y^{m-1}\left(1-y\right)^{n-m} \\ &= n \binom{n-1}{k-1} y^{k-1}(1-y)^{n-k} \end{align*} \begin{align*} &&1 &= \int_0^1 f_{Y_k}(y) \d y \\ &&&= \int_0^1 n \binom{n-1}{k-1} y^{k-1}(1-y)^{n-k} \d y \\ &&&= n \binom{n-1}{k-1} \int_0^1 y^{k-1}(1-y)^{n-k} \d y \\ \Rightarrow && \frac{1}{n \binom{n-1}{k-1}} &= \int_0^1 y^{k-1}(1-y)^{n-k} \d y \\ \end{align*}
  3. \begin{align*} && \mathbb{E}(Y_k) &= \int_0^1 y f_{Y_k}(y) \d y \\ &&&= \int_0^1 n \binom{n-1}{k-1} y^{k}(1-y)^{n-k} \\ &&&= n \binom{n-1}{k-1}\int_0^1 y^{k}(1-y)^{n-k} \d y \\ &&&= n \binom{n-1}{k-1}\int_0^1 y^{k+1-1}(1-y)^{n+1-(k+1)} \d y \\ &&&= n \binom{n-1}{k-1} \frac{1}{(n+1) \binom{n}{k}}\\ &&&= \frac{n}{n+1} \cdot \frac{k}{n} \\ &&&= \frac{k}{n+1} \end{align*}

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
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
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
2003 Paper 3 Q2
D: 1700.0 B: 1484.0
generalised binomial theorem binomial series combinatorial identity summation central binomial coefficient series convergence proof

Show that $\ds ^{2r} \! {\rm C}_r =\frac{1\times3\times\dots\times (2r-1)}{r!} \, \times 2^r \;, $ for \(r\ge1\,\).

  1. Give the first four terms of the binomial series for \(\l 1 - p \r^{-\frac12}\). By choosing a suitable value for \(p\) in this series, or otherwise, show that $$ \displaystyle \sum_{r=0}^\infty \frac{ {\vphantom {\A}}^{2r} \! {\rm C}_r }{ 8^r} = \sqrt 2 \; .$$
  2. Show that $$ \displaystyle \sum_{r=0}^\infty \frac{\l 2r + 1 \r \; {\vphantom{A}}^{2r} \! {\rm C} _r }{ 5^r} =\big( \sqrt 5\big)^3 \;. $$
[{\bf Note: } $ {\vphantom{A}}^n {\rm C}_r $ is an alternative notation for $\ds \ \binom n r \, \( for \)r\ge1\,\(, and \) {\vphantom{A}}^0 {\rm C}_0 =1 $ .]

Solution: \begin{align*} \binom{2r}{r} &= \frac{(2r)!}{r!r!} \\ &= \frac{1 \cdot 2 \cdot 3 \cdot 4 \cdots (2r-1)(2r)}{r! r!} \\ &= \frac{1 \cdot 3 \cdot 5 \cdots (2r-1) \cdot (2 \cdot 1) \cdot (2 \cdot 2) \cdots (2 \cdot r)}{r!}{r!} \\ &= \frac{1\cdot 3 \cdots (2r-1) \cdot 2^r \cdot 1 \cdot 2 \cdots r}{r!r!} \\ &= \frac{1\cdot 3 \cdots (2r-1) \cdot 2^r \cdot r!}{r!r!} \\ &= \frac{1\cdot 3 \cdots (2r-1)}{r!} \cdot 2^r \end{align*} which is what we wanted to show

  1. \begin{align*} (1 - p)^{-\frac12} &= 1 + \left ( -\frac12 \right )(-p) + \frac{1}{2!} \left (-\frac12 \right )\left (-\frac32 \right )(-p)^2 + \ldots \\ & \quad \quad \quad \cdots +\frac{1}{3!} \left (-\frac12 \right )\left (-\frac32 \right )\left (-\frac52 \right )(-p)^3 + O(p^4) \\ &= \boxed{1 + \frac{1}{2}p + \frac{3}{8}p^2 + \frac{5}{16}p^3} + O(p^4) \end{align*} More generally: \begin{align*} \binom{-\frac{1}{2}}{k} &=\frac{(-\frac{1}{2})\cdot(-\frac{1}{2} -1)\cdots(-\frac12 -k+1)}{k!} \\ &= \frac{(-1)(-3)(-5)\cdots(-(2k-1))}{k!2^k} \\ &= \frac{(-1)^k(1)(3)(5)\cdots((2k-1))}{k!2^k} \\ &= (-1)^k \frac{1}{4^k}\binom{2k}{k} \\ \end{align*} Therefore, \begin{align*} \sqrt{2} = \left (1-\frac12 \right)^{-\frac12} &= \sum_{r=0}^{\infty} \binom{-\frac12}{r} \left (-\frac12 \right )^r \tag{\(\frac12 < 1\) so series is valid} \\ &= \sum_{r=0}^{\infty} (-1)^r \frac{1}{4^r}\binom{2r}{r} \left (-\frac12 \right )^r \\ &= \sum_{r=0}^{\infty} \frac{1}{8^r}\binom{2r}{r} \end{align*}, which is what we wanted to show.
  2. \begin{align*} p(1-p^2)^{-\frac12} &= \sum_{r=0}^{\infty} \binom{-\frac12}{r} \left (-p^2 \right )^rp \\ &= \sum_{r=0}^{\infty} \frac{1}{4^r}\binom{2r}{r} p^{2r+1} \end{align*} Differentiating with respect to \(p\), \begin{align*} (1-p^2)^{-\frac12} +p^2(1-p^2)^{-\frac32} &= \sum_{r=0}^{\infty} \frac{1}{4^r}(2r+1)\binom{2r}{r} p^{2r} \\ (1-p^2)^{-\frac32} &= \sum_{r=0}^{\infty} \frac{1}{4^r}(2r+1)\binom{2r}{r} p^{2r} \end{align*} Letting \(p = \frac{2}{\sqrt{5}}\), and \(|\frac2{\sqrt{5}}| < 1\) we have \begin{align*} \left (1-\frac45 \right )^{-\frac32} &= \sum_{r=0}^{\infty} \frac{1}{5^r}(2r+1)\binom{2r}{r} \\ (\sqrt{5})^3 &= \sum_{r=0}^{\infty} \frac{1}{5^r}(2r+1)\binom{2r}{r} \end{align*} (Alternative) \begin{align*} (\sqrt5)^3 &= \left ( \frac{1}{5} \right )^{-\frac32} \\ &= \left ( 1- \frac{4}{5} \right )^{-\frac32} \\ &= \sum_{r=0}^{\infty} \binom{-\frac32}{r} \left (-\frac45 \right)^r \\ &= \sum_{r=0}^{\infty} \binom{-\frac12}{r} \frac{-\frac32-(r-1)}{-\frac12} \left (-\frac45 \right)^r \\ &= \sum_{r=0}^{\infty} \binom{-\frac12}{r} (2r+1) \left (-\frac45 \right)^r \\ &= \sum_{r=0}^{\infty} (-1)^r \frac{1}{4^r}\binom{2r}{r} (2r+1) \left (-\frac45 \right)^r \\ &= \sum_{r=0}^{\infty}(2r+1)\binom{2r}{r} \left (\frac15 \right)^r \\ (\sqrt{5})^3 &= \sum_{r=0}^{\infty}\frac{1}{5^r}(2r+1)\binom{2r}{r} \\ \end{align*}

View
1996 Paper 1 Q12
D: 1484.0 B: 1485.4
probability hypergeometric distribution combinatorics binomial coefficients expected value order statistics combinatorial identity sampling without replacement

An examiner has to assign a mark between 1 and \(m\) inclusive to each of \(n\) examination scripts (\(n\leqslant m\)). He does this randomly, but never assigns the same mark twice. If \(K\) is the highest mark that he assigns, explain why \[ \mathrm{P}(K=k)=\left.\binom{k-1}{n-1}\right/\binom{m}{n} \] for \(n\leqslant k\leqslant m,\) and deduce that \[ \sum_{k=n}^{m}\binom{k-1}{n-1}=\binom{m}{n}\,. \] Find the expected value of \(K\).

Solution: If the highest mark is \(k\), then there are \(n-1\) remaining marks to give, and they have to be chosen from the numbers \(1, 2, \ldots, k-1\), ie in \(\binom{k-1}{n-1}\) ways. There are \(n\) numbers to be chosen from \(1, 2, \ldots, m\) in total, therefore \(\displaystyle \mathbb{P}(K=k) = \left.\binom{k-1}{n-1} \right/ \binom{m}{n}\) Since \(K\) can take any of the values \(n, \cdots, m\), we must have \begin{align*} && 1 &= \sum_{k=n}^m \mathbb{P}(K=k) \\ &&&= \sum_{k=n}^m \left.\binom{k-1}{n-1} \right/ \binom{m}{n} \\ \Rightarrow && \binom{m}{n} &= \sum_{k=n}^m \binom{k-1}{n-1} \\ \\ && \mathbb{E}(K) &= \sum_{k=n}^m k \cdot \mathbb{P}(K=k) \\ &&&= \sum_{k=n}^m k \cdot \left.\binom{k-1}{n-1} \right/ \binom{m}{n} \\ &&&= n\binom{m}{n}^{-1} \sum_{k=n}^m \frac{k}{n} \cdot \binom{k-1}{n-1} \\ &&&= n\binom{m}{n}^{-1} \sum_{k=n}^m \binom{k}{n} \\ &&&= n\binom{m}{n}^{-1} \sum_{k=n+1}^{m+1} \binom{k-1}{n+1-1} \\ &&&= n\binom{m}{n}^{-1} \binom{m+1}{n+1} \\ &&&= n \cdot \frac{m+1}{n+1} \end{align*}

View
1994 Paper 1 Q13
D: 1500.0 B: 1512.0
hypergeometric distribution probability expectation indicator random variables combinatorial identity sampling without replacement binomial coefficients

I have a bag containing \(M\) tokens, \(m\) of which are red. I remove \(n\) tokens from the bag at random without replacement. Let \[ X_{i}=\begin{cases} 1 & \mbox{ if the ith token I remove is red;}\\ 0 & \mbox{ otherwise.} \end{cases} \] Let \(X\) be the total number of red tokens I remove.

  1. Explain briefly why \(X=X_{1}+X_{2}+\cdots+X_{n}.\)
  2. Find the expectation \(\mathrm{E(}X_{i}).\)
  3. Show that \(\mathrm{E}(X)=mn/M\).
  4. Find \(\mathrm{P}(X=k)\) for \(k=0,1,2,\ldots,n\).
  5. Deduce that \[ \sum_{k=1}^{n}k\binom{m}{k}\binom{M-m}{n-k}=m\binom{M-1}{n-1}. \]

Solution:

  1. The left hand side counts the number of red tokens we have taken. The right hand side counts the number of red tokens we have taken at each point, across all points. Therefore these must be the same.
  2. \(\E[X_i] = \mathbb{P}(i\text{th token is red}) = \frac{m}{M}\) (since there is nothing special about the \(i\)th token.
  3. Therefore \(\E[X] = \E[X_1 + \cdots + X_n] = n\E[X_i] = \frac{nm}{M}\)
  4. \(\mathbb{P}(X=k) = \binom{m}{k}\binom{M-m}{n-k}/\binom{M}{n}\) since this is the number of ways we can choose \(k\) of the \(m\) red objects, \(n-k\) of the \(M-m\) non-red objects divided by the total number of ways we can choose our \(n\) tokens.
  5. \(\,\) \begin{align*} && \frac{mn}{M} &= \E[X] \\ &&&= \sum_{k=1}^n k \mathbb{P}(X=k) \\ &&&= \sum_{k=1}^n k \binom{m}{k}\binom{M-m}{n-k}/\binom{M}{n} \\ \Rightarrow && \sum_{k=1}^n k \binom{m}{k}\binom{M-m}{n-k} &= m \frac{n}{M} \binom{M}{n} = m \binom{M-1}{n-1} \end{align*}
This question is a nice example of how to find the mean of the hypergeometric distribution

View
1992 Paper 1 Q5
D: 1484.0 B: 1500.0
polynomials factorization differentiation power sums product expansion combinatorial identity proof

Let \(\mathrm{p}_{0}(x)=(1-x)(1-x^{2})(1-x^{4}).\) Show that \((1-x)^{3}\) is a factor of \(\mathrm{p}_{0}(x).\) If \(\mathrm{p}_{1}(x)=x\mathrm{p}_{0}'(x)\) show, by considering factors of the polynomials involved, that \(\mathrm{p}_{0}'(1)=0\) and \(\mathrm{p}_{1}'(1)=0.\) By writing \(\mathrm{p}_{0}(x)\) in the form \[ \mathrm{p}_{0}(x)=c_{0}+c_{1}x+c_{2}x^{2}+c_{3}x^{3}+c_{4}x^{4}+c_{5}x^{5}+c_{6}x^{6}+c_{7}x^{7}, \] deduce that \begin{alignat*}{2} 1+2+4+7 & \quad=\quad & & 3+5+6\\ 1^{2}+2^{2}+4^{2}+7^{2} & \quad=\quad & & 3^{2}+5^{2}+6^{2}. \end{alignat*} Show that we can write the integers \(1,2,\ldots,15\) in some order as \(a_{1},a_{2},\ldots,a_{15}\) in such a way that \[ a_{1}^{r}+a_{2}^{r}+\cdots+a_{8}^{r}=a_{9}^{r}+a_{10}^{r}+\cdots+a_{15}^{r} \] for \(r=1,2,3.\)

Solution: \begin{align*} && p_0(x) &= (1-x)(1-x^2)(1-x^4) \\ &&&= (1-x)(1-x)(1+x)(1-x^2)(1+x^2) \\ &&&= (1-x)^2 (1+x)(1-x)(1+x)(1+x^2) \\ &&&= (1-x)^3 (1+x)^2 (1+x^2) \end{align*} \begin{align*} && p_0'(x) &= 3(1-x)^2(1+x)^2(1+x^2) + (1-x)^3 q(x) \\ \Rightarrow && p_0'(1) &= 3 \cdot 0 \cdots + 0 \cdots \\ &&&= 0 \\ && p_1'(x) &= p_0(x) + xp'_0(x) \\ \Rightarrow && p_1'(1) &= p_0(1) + 1\cdot p_0'(1) \\ &&&= 0 + 1 \cdot 0 \\ &&&= 0 \end{align*} Notice that \(p_0(x) = (1-x-x^2+x^3)(1-x^4) = 1-x-x^2+x^3-x^4+x^5+x^6-x^7\), so: \(p'_0(x) = -1-2x+3x^2-4x^3+5x^4+6x^5-7x^6 \Rightarrow p'_0(1) = 0 = -1 -2 -4 -7 + 3 + 5+6\). \((xp'_1(1))' = 0 = -1^2-2^2-4^2-7^2 + 3^2 + 5^2 + 6^2\). Consider \(q_0(x) = (1-x)(1-x^2)(1-x^4)(1-x^8)\), then \((1-x)^4\) is a factor, so in particular we know \(q_0(1), (xq_0(x))'|_{x=1} = 0,(x(xq_0(x))')'|_{x=1} = 0\), and so: \(q_0(x) = 1-x-x^2+x^3-x^4+x^5+x^6-x^7 - x^8+x^9+x^{10}-x^{11}+x^{12}-x^{13}-x^{14}+x^{15}\), and so: \(1^r+2^r+4^r+7^r+8^r+11^r+13^r+14^r = 3^r+5^r+6^r+9^r+10^r+12^r+15^r\) for \(r = 1,2,3\)

View
1987 Paper 2 Q5
D: 1500.0 B: 1500.0
sequences series Lagrange inversion inverse function higher derivatives power series convergence combinatorial identity

If \(y=\mathrm{f}(x)\), then the inverse of \(\mathrm{f}\) (when it exists) can be obtained from Lagrange's identity. This identity, which you may use without proof, is \[ \mathrm{f}^{-1}(y)=y+\sum_{n=1}^{\infty}\frac{1}{n!}\frac{\mathrm{d}^{n-1}}{\mathrm{d}y^{n-1}}\left[y-\mathrm{f}\left(y\right)\right]^{n}, \] provided the series converges.

  1. Verify Lagrange's identity when \(\mathrm{f}(x)=\alpha x\), \((0<\alpha<2)\).
  2. Show that one root of the equation \[ \tfrac{1}{2}=x-\tfrac{1}{4}x^{3} \] is \[ x=\sum_{n=0}^{\infty}\frac{\left(3n\right)!}{n!\left(2n+1\right)!2^{4n+1}} \]
  3. Find a solution for \(x\), as a series in \(\lambda,\) of the equation \[ x=\mathrm{e}^{\lambda x}. \]
[You may assume that the series in part \((ii) \)converges, and that the series in part \((iii) \)converges for suitable \(\lambda\).]

Solution:

  1. If \(f(x) = \alpha x\) then \(f^{-1}(x) = \frac{1}{\alpha}x\). \begin{align*} && \frac{\d^{n-1}}{\d y^{n-1}} [y - \alpha y]^n &= \frac{\d^{n-1}}{\d y^{n-1}} [(1 - \alpha)^n y^n] \\ && &= (1-\alpha)^n n! y \\ \Rightarrow && y + \sum_{n=1}^{\infty} \frac{1}{n!}\frac{\d^{n-1}}{\d y^{n-1}} [y - \alpha y]^n &= y +\sum_{n=1}^{\infty} (1-\alpha)^ny \\ &&&= y + y\l \frac{1}{1-(1-\alpha)}-1 \r \\ &&&= \frac{1}{\alpha}y \end{align*} Where we can sum the geometric progression if \(|1-\alpha| < 1 \Leftrightarrow 0 < \alpha < 2\)
  2. Suppose that \(f(x) = x-\frac14x^3\). We would like to find \(f^{-1}(\frac12)\). \begin{align*} && \frac{\d^{n-1}}{\d y^{n-1}} [y - (y+\frac14 y^3)]^n &= \frac{\d^{n-1}}{\d y^{n-1}} [\frac1{4^n} y^{3n}] \\ && &= \frac{1}{4^n} \frac{(3n)!}{(2n+1)!} y^{2n+1} \\ \Rightarrow && f^{-1}(\frac12) &= \frac12 + \sum_{n=1}^{\infty} \frac{1}{4^n} \frac{(3n)!}{n!(2n+1)!} \frac{1}{2^{2n+1}} \\ &&&= \frac12 + \sum_{n=1}^{\infty} \frac{(3n)!}{n!(2n+1)!} \frac{1}{2^{4n+1}} \\ \end{align*} Since when \(n = 0\) \(\frac{0!}{0!1!} \frac{1}{2^{0+1}} = \frac12\) we can include the wayward \(\frac12\) in our infinite sum and so we have the required result.
  3. Consider \(f(x) = x - e^{\lambda x}\) we are interested in \(f^{-1}(0)\). \begin{align*} && \frac{\d^{n-1}}{\d y^{n-1}} [y - (y-e^{\lambda y})]^n &= \frac{\d^{n-1}}{\d y^{n-1}} [e^{n\lambda y}] \\ &&&= n^{n-1} \lambda^{n-1}e^{n \lambda y} \\ \Rightarrow && f^{-1}(0) &= \sum_{n=1}^\infty \frac{1}{n!} n^{n-1} \lambda^{n-1} \end{align*} We don't care about convergence, but it's worth noting this has a radius of convergence of \(\frac{1}{e}\) (ie this series is valid if \(|\lambda| < \frac1e\)).

View