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