Problems

Filters
Clear Filters

4 problems found

2014 Paper 2 Q13
D: 1600.0 B: 1469.5
probability uniform distribution discrete random variable expectation birthday problem summation identity proof

A random number generator prints out a sequence of integers \(I_1, I_2, I_3, \dots\). Each integer is independently equally likely to be any one of \(1, 2, \dots, n\), where \(n\) is fixed. The random variable \(X\) takes the value \(r\), where \(I_r\) is the first integer which is a repeat of some earlier integer. Write down an expression for \(\mathbb{P}(X=4)\).

  1. Find an expression for \(\mathbb{P}(X=r)\), where \(2\le r\le n+1\). Hence show that, for any positive integer \(n\), \[ \frac 1n + \left(1-\frac1n\right) \frac 2 n + \left(1-\frac1n\right)\left(1-\frac2n\right) \frac3 n + \cdots \ = \ 1 \,. \]
  2. Write down an expression for \(\mathbb{E}(X)\). (You do not need to simplify it.)
  3. Write down an expression for \(\mathbb{P}(X\ge k)\).
  4. Show that, for any discrete random variable \(Y\) taking the values \(1, 2, \dots, N\), \[ \mathbb{E}(Y) = \sum_{k=1}^N \mathbb{P}(Y\ge k)\,. \] Hence show that, for any positive integer \(n\), \[ \left(1-\frac{1^2}n\right) + \left(1-\frac1n\right)\left(1-\frac{2^2}n\right) + \left(1-\frac1n\right)\left(1-\frac{2}n\right)\left(1-\frac{3^2}n\right) + \cdots \ = \ 0. \]

Solution: \begin{align*} && \mathbb{P}(X > 4) &= 1 \cdot \frac{n-1}{n} \cdot \frac{n-2}{n} \cdot \frac{n-3}{n} \\ && \mathbb{P}(X > 3) &= 1 \cdot \frac{n-1}{n} \cdot \frac{n-2}{n} \\ \Rightarrow && \mathbb{P}(X =4) &= \mathbb{P}(X > 3) - \mathbb{P}(X > 4) \\ &&&= \frac{(n-1)(n-2)}{n^2} \left (1 - \frac{n-3}{n} \right) \\ &&&= \frac{3(n-1)(n-2)}{n^3} \end{align*}

  1. Notice that \begin{align*} && \mathbb{P}(X > r) &= \frac{n-1}{n} \cdots \frac{n-r+1}{n} \\ \Rightarrow && \mathbb{P}(X = r) &= \frac{n-1}{n} \cdots \frac{n-r+2}{n} \left (1 - \frac{n-r+1}{n} \right) \\ &&&= \frac{(n-1)\cdots(n-r+2)(r-1)}{n^{r-1}} \\ &&&= \left (1 - \frac{1}n \right)\left (1 - \frac{2}{n} \right) \cdots \left (1 - \frac{r-2}{n} \right) \frac{r-1}{n} \\ \Rightarrow && 1 &= \sum \mathbb{P}(X = r) \\ &&&= \sum_{r=2}^{n+1} \mathbb{P}(X = r) \\ &&&= \frac 1n + \left(1-\frac1n\right) \frac 2 n + \left(1-\frac1n\right)\left(1-\frac2n\right) \frac3 n + \cdots \end{align*}
  2. \(\,\) \begin{align*} \mathbb{E}(X) &= \sum_{r=2}^{n+1} r\cdot\mathbb{P}(X = r) \\ &= \frac 2n + \left(1-\frac1n\right) \frac {2\cdot3} n + \left(1-\frac1n\right)\left(1-\frac2n\right) \frac{3\cdot4} n + \cdots \end{align*}
  3. \(\displaystyle \mathbb{P}(X \geq k) = \frac{n-1}{n} \cdots \frac{n-r+2}{n}\)
  4. \(\,\) \begin{align*} && \mathbb{E}(Y) &= \sum_{r=1}^N r \cdot \mathbb{P}(Y = r) \\ &&&= \sum_{r=1}^N \sum_{j=1}^r \mathbb{P}(Y = r) \\ &&&= \sum_{j=1}^N \sum_{r=j}^N \mathbb{P}(Y=r) \\ &&&= \sum_{j=1}^N \mathbb{P}(Y \geq j) \end{align*} Let \(P_k = \left(1-\frac1n\right)\left(1-\frac2n\right) \cdots \left(1-\frac1n\right)\left(1-\frac{k}n\right) \) \begin{align*} && \mathbb{E}(X) &= P_1 \frac{1 \cdot 2 }{n} + P_2 \cdot \frac{2 \cdot 3}{n} + \cdots + P_k \cdot \frac{k(k+1)}{n} + \cdots \\ && &= \sum_{k=1}^{n} \frac{k^2}{n}P_k + \sum_{k=1}^{n} \frac{k}{n}P_k \\ && \text{Using the identity } & \frac{k}{n}P_k = \frac{k}{n} \prod_{i=1}^{k-1} \left(1-\frac{i}{n}\right) = P_k - P_{k+1}: \\ && \sum_{k=1}^{n} \frac{k}{n}P_k &= (P_1 - P_2) + (P_2 - P_3) + \cdots + (P_n - P_{n+1}) \\ && &= P_1 - P_{n+1} = 1 - 0 = 1 \\ \\ \Rightarrow && \mathbb{E}(X) &= \sum_{k=1}^{n} \frac{k^2}{n}P_k + 1 \\ && &= \mathbb{P}(X \geq 1) + \mathbb{P}(X \geq 2) + \mathbb{P}(X \geq 3) + \cdots \\ && &= 1 + P_1 + P_2 + P_3 + \cdots \\ && &= 1 + \sum_{k=1}^{n} P_k \\ \\ \Rightarrow && 1 + \sum_{k=1}^{n} P_k &= \sum_{k=1}^{n} \frac{k^2}{n}P_k + 1 \\ \Rightarrow && \sum_{k=1}^{n} P_k &= \sum_{k=1}^{n} \frac{k^2}{n}P_k \\ \Rightarrow && 0 &= \sum_{k=1}^{n} P_k \left( 1 - \frac{k^2}{n} \right) \end{align*}

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
2007 Paper 1 Q1
D: 1500.0 B: 1500.0
combinatorics counting balanced number digit sum summation identity enumeration

A positive integer with \(2n\) digits (the first of which must not be \(0\)) is called a balanced number if the sum of the first \(n\) digits equals the sum of the last \(n\) digits. For example, \(1634\) is a \(4\)-digit balanced number, but \(123401\) is not a balanced number.

  1. Show that seventy \(4\)-digit balanced numbers can be made using the digits \(0, 1, 2, 3\) and \(4\).
  2. Show that \(\frac16 {k \left( k+1 \right) \left( 4k+5 \right) }\) \(4\)-digit balanced numbers can be made using the digits \(0\) to \(k\). You may use the identity $\displaystyle \sum _{r=0}^{n} r^2 \equiv \tfrac{1}{6} {n \left( n+1 \right) \left( 2n+1 \right) } \;$.

Solution:

  1. For each number from \(1\) to \(8\) (4+4), we can count the number of ways it can be achieved in any way, or without including a leading \(0\). \begin{array}{c|c|c|c} \text{total} & \text{ways with }0 & \text{ways without } 0 & \text{comb}\\ \hline 8 & 1 & 1 & 1\\ 7 & 2 & 2 & 4 \\ 6 & 3 & 3 & 9 \\ 5 & 4 & 4 & 16 \\ 4 & 5 & 4 & 20 \\ 3 & 4 & 3 & 12 \\ 2 & 3 & 2 & 6 \\ 1 & 2 & 1 & 2 \\ \hline &&& 70 \end{array}
  2. For \(2k\) to \(k+1\) there are \(1 \times 1 + 2 \times 2 + \cdots i\times i+\cdots + k\times k\) ways to achieve this, (we can choose anything from \(k\) to \(k-i+1\) for the first digit, and we can never have a \(0\). For \(1\) to \(k\) we can have \(1 \times 2 + 2 \times 3 + \cdots + k \times (k+1)\) since we cannot start with a \(0\), but can have anything less than or equal to \(i\) for the first digit, and then with the \(0\) we can have the same thing starting with \(0\). Hence the answer is: \begin{align*} && S &= \sum_{i=1}^k i^2 + \sum_{i=1}^k i (i+1) \\ &&&= 2\sum_{i=1}^k i^2 + \sum_{i=1}^k i \\ &&&= \frac{1}{3} k(k+1)(2k+1) + \frac12k(k+1) \\ &&&= k(k+1) \left (\frac{2k+1}{3} + \frac{1}{2} \right) \\ &&&= \frac16 k(k+1)(4k+2+3) \\ &&&= \frac16 k(k+1)(4k+5) \end{align*}

View
1997 Paper 3 Q1
D: 1700.0 B: 1500.0
Taylor series exponential function series expansion polynomial multiplication summation identity Maclaurin series

  1. By considering the series expansion of \((x^2+5x+4){\rm \; e}^x\) show that \[10{\rm\, e}=4+\frac{3^2}{1!}+\frac{4^2}{2!}+\frac{5^2}{3!}+\cdots\;.\]
  2. Show that \[5{\rm\, e}=1+\frac{2^2}{1!}+\frac{3^2}{2!}+\frac{4^2}{3!}+\cdots\;.\]
  3. Evaluate \[1+\frac{2^3}{1!}+\frac{3^3}{2!}+\frac{4^3}{3!}+\cdots\;.\]

Solution:

  1. \begin{align*} (x^2+5x+4)e^x &= \sum_{k=0}^\infty \frac{1}{k!} x^{k+2}+\sum_{k=0}^\infty \frac{5}{k!} x^{k+1}+\sum_{k=0}^\infty \frac{4}{k!} x^{k} \\ &= \sum_{k=0}^{\infty} \l \frac{1}{k!}+\frac{5}{(k+1)!}+\frac{4}{(k+2)!} \r x^{k+2} + 5x+4+4x \\ &= 4 + 9x + \sum_{k=0}^{\infty} \l \frac{(k+2)(k+1)}{(k+2)!}+\frac{5(k+2)}{(k+2)!}+\frac{4}{(k+2)!} \r x^{k+2}\\ &= 4 + 9x + \sum_{k=0}^{\infty} \l \frac{k^2+3k+2+5k+10+4}{(k+2)!} \r x^{k+2}\\ &= 4 + 9x + \sum_{k=0}^{\infty} \frac{(k+4)^2}{(k+2)!} x^{k+2}\\ &= 4 + 9x + \sum_{k=2}^{\infty} \frac{(k+2)^2}{k!} x^{k}\\ \end{align*} So when \(x = 1\) we have \[10e = 4 + \frac{3^2}{1!} + \frac{4^2}{2!} + \frac{5^2}{3!} + \cdots \]
  2. \begin{align*} (x^2+3x+1)e^x &= \sum_{k=0}^\infty \frac{1}{k!}x^{k+2}+\sum_{k=0}^\infty 3\frac{1}{k!}x^{k+1} + \sum_{k=0}^{\infty} \frac{1}{k!} x^k \\ &= 1+3x+\sum_{k=1}^{\infty} \l \frac1{(k-1)!}+\frac{3}{k!} + \frac{1}{(k+1)!} \r x^{k+1} \\ &= 1+3x+\sum_{k=1}^{\infty} \frac{(k+1)k + 3(k+1)+1}{(k+1)!}x^{k+1} \\ &= 1+3x+\sum_{k=1}^{\infty} \frac{k^2+4k+4}{(k+1)!}x^{k+1} \\ &= 1+3x+\sum_{k=0}^{\infty} \frac{(k+2)^2}{(k+1)!}x^{k+1} \\ &=1+3x+ \sum_{k=1}^{\infty} \frac{(k+1)^2}{k!}x^k \end{align*} Plugging in \(x=1\) we get the desired result.
  3. \begin{align*} && xe^x &= \sum_{k=0}^{\infty} \frac{x^{k+1}}{k!} \\ x\frac{\d}{\d x} : && x(1+x)e^x &= \sum_{k=0}^{\infty} \frac{(k+1)x^{k+1}}{k!} \\ x\frac{\d}{\d x} : && x(x(1+x)+1+2x)e^x &= \sum_{k=0}^{\infty} \frac{(k+1)^2x^{k+1}}{k!} \\ &&(x^3+3x^2+x)e^x &= \sum_{k=0}^{\infty} \frac{(k+1)^2x^{k+1}}{k!} \\ \frac{\d}{\d x} : && e^x(x^3+3x^2+x+3x^2+6x+1) &=\sum_{k=0}^{\infty} \frac{(k+1)^3x^{k}}{k!} \\ \Rightarrow && 15e &= 1 + \frac{2^3}{1!} + \frac{3^3}{2!} + \cdots \end{align*}

View