STEP II 2014 13

1 Like

P(X=4)=1\times\frac{n-1}n\times\frac{n-2}n\times\frac3n=\left(1-\frac1n\right)\left(1-\frac2n\right)\frac3n

Part (i)
Generalising the above:

\begin{align} P(X=r)&=\left(1-\frac1n\right)\left(1-\frac2n\right)\cdots\left(1-\frac{r-2}n\right)\frac{r-1}n\\ &=\frac{r-1}n\prod_{i=1}^{r-2}\left(1-\frac in\right) \end{align}

Hence, the expression given is equivalent to:

P(X=2)+P(X=3)+P(X=4)+\cdots+P(X=n+1)=1

which is necessarily true as there must be a repeat within n+1 numbers (pigeonhole principle).
Part (ii)

\begin{align} E(X)&=\sum_{k=2}^{n+1} kP(X=k)\\ &=\sum_{k=2}^{n+1} \left[\frac{k(k-1)}n\prod_{i=1}^{k-2}\left(1-\frac in\right)\right] \end{align}

Part (iii)
X\geq k exactly when the first k-1 numbers have no repeats.

\begin{align} P(X\geq k)&=\left(1-\frac1n\right)\left(1-\frac2n\right)\cdots\left(1-\frac{k-2}n\right)\\ &=\prod_{i=1}^{k-2}\left(1-\frac in\right) \end{align}

Part (iv)

\begin{alignat}{6} E(Y)&=\rlap{\sum_{k=1}^NkP(Y=k)}\\\\ &=P(Y=1)&&+2P(Y=2)&&+3P(Y=3)&&+\cdots&&+NP(Y=N)\\ &=(P(Y=1)&&+P(Y=2)&&+P(Y=3)&&+\cdots&&+P(Y=N))\\ &&&+(P(Y=2)&&+P(Y=3)&&+\cdots&&+P(Y=N))\\ &&&&&+(P(Y=3)&&+\cdots&&+P(Y=N))\\ &&&&&&&&&\qquad\ \ \ \ \ \ \,\vdots\\ &&&&&&&&&+P(Y=N)\\ &=P(Y\geq1)&&+P(Y\geq2)&&+P(Y\geq3)&&+\cdots&&+P(Y\geq N)\\ &=\rlap{\sum_{k=1}^NP(Y\geq k)} \end{alignat}

Applying this to our results from Parts (ii) and (iii) and using the result from Part (i):

\begin{align} \sum_{k=2}^{n+1} \left[\frac{k(k-1)}n\prod_{i=1}^{k-2}\left(1-\frac in\right)\right]&=\sum_{k=1}^{n+1}\left[\prod_{i=1}^{k-2}\left(1-\frac in\right)\right]\\ \sum_{k=2}^{n+1} \left[\frac{k(k-1)}n\prod_{i=1}^{k-2}\left(1-\frac in\right)\right]&=1+\sum_{k=2}^{n+1}\left[\prod_{i=1}^{k-2}\left(1-\frac in\right)\right]\\ \sum_{k=2}^{n+1} \left[\frac{k(k-1)}n\prod_{i=1}^{k-2}\left(1-\frac in\right)\right]&=\sum_{k=2}^{n+1}P(X=k)+\sum_{k=2}^{n+1}\left[\prod_{i=1}^{k-2}\left(1-\frac in\right)\right]\\ \sum_{k=2}^{n+1} \left[\frac{k(k-1)}n\prod_{i=1}^{k-2}\left(1-\frac in\right)\right]&=\sum_{k=2}^{n+1}\left[\frac{k-1}n\prod_{i=1}^{k-2}\left(1-\frac in\right)\right]+\sum_{k=2}^{n+1}\left[\prod_{i=1}^{k-2}\left(1-\frac in\right)\right]\\ \sum_{k=2}^{n+1} \left[\frac{k(k-1)}n\prod_{i=1}^{k-2}\left(1-\frac in\right)\right]&=\sum_{k=2}^{n+1}\left[\frac{k-1}n\prod_{i=1}^{k-2}\left(1-\frac in\right)+\prod_{i=1}^{k-2}\left(1-\frac in\right)\right]\\ \sum_{k=2}^{n+1} \left[\frac{k(k-1)}n\prod_{i=1}^{k-2}\left(1-\frac in\right)\right]&=\sum_{k=2}^{n+1}\left[\left(1+\frac{k-1}n\right)\prod_{i=1}^{k-2}\left(1-\frac in\right)\right]\\ \sum_{k=2}^{n+1}\left[\left(1+\frac{k-1}n-\frac{k(k-1)}n\right)\prod_{i=1}^{k-2}\left(1-\frac in\right)\right]&=0\\ \sum_{k=2}^{n+1}\left[\left(1-\frac{(k-1)^2}n\right)\prod_{i=1}^{k-2}\left(1-\frac in\right)\right]&=0\\ \end{align}

which is exactly the equation we were required to prove, since any terms containing \left(1-\frac nn\right) are equal to 0.

2 Likes

Absolute beast of a latex answer haha

1 Like

Yeah it took quite a lot copy and pasting

1 Like