IMC 2025 Problem 9

Let $n$ be a positive integer. Consider the following random process which produces $n$ sequence of $n$ distinct positive integers $X_1, X_2 \ldots, X_n$ . First, $X_1$ is chosen randomly with $\mathbb{P}\left(X_1=i\right)=2^{-i}$ for every positive integer $i$ . For $1 \leq j \leq n-1$ . having chosen $X_1, \ldots, X_j$ , arrange the remaining positive integers in increasing order as $n_1<n_2<$ $\cdots$ , and choose $X_{j+1}$ randomly with $\mathbb{P}\left(X_{j+1}=n_i\right)=2^{-i}$ for every positive integer $i$ . Let $Y_n=\max \left\{X_1, \ldots, X_n\right\}$ . Show that $$\mathbb{E}\left[Y_n\right]=\sum_{i=1}^n \frac{2^i}{2^i-1}$$ where $\mathbb{E}\left[Y_n\right]$ is the expected value of $Y_n$ .