IMO Shortlist, 2016

We first show that $a=\frac{4}{9}$ is admissible. For each $2 \leqslant k \leqslant n$, by the Cauchy-Schwarz Inequality, we have
$$\left(x_{k-1}+\left(x_{k}-x_{k-1}\right)\right)\left(\frac{(k-1)^{2}}{x_{k-1}}+\frac{3^{2}}{x_{k}-x_{k-1}}\right) \geqslant(k-1+3)^{2}$$
which can be rewritten as
$$\frac{9}{x_{k}-x_{k-1}} \geqslant \frac{(k+2)^{2}}{x_{k}}-\frac{(k-1)^{2}}{x_{k-1}} \tag{2}$$
Summing (2) over $k=2,3, \ldots, n$ and adding $\frac{9}{x_{1}}$ to both sides, we have
$$9 \sum_{k=1}^{n} \frac{1}{x_{k}-x_{k-1}} \geqslant 4 \sum_{k=1}^{n} \frac{k+1}{x_{k}}+\frac{n^{2}}{x_{n}}>4 \sum_{k=1}^{n} \frac{k+1}{x_{k}}$$
This shows (1) holds for $a=\frac{4}{9}$.

Next, we show that $a=\frac{4}{9}$ is the optimal choice. Consider the sequence defined by $x_{0}=0$ and $x_{k}=x_{k-1}+k(k+1)$ for $k \geqslant 1$, that is, $x_{k}=\frac{1}{3} k(k+1)(k+2)$. Then the left-hand side of (1) equals
$$\sum_{k=1}^{n} \frac{1}{k(k+1)}=\sum_{k=1}^{n}\left(\frac{1}{k}-\frac{1}{k+1}\right)=1-\frac{1}{n+1}$$
while the right-hand side equals
$$a \sum_{k=1}^{n} \frac{k+1}{x_{k}}=3 a \sum_{k=1}^{n} \frac{1}{k(k+2)}=\frac{3}{2} a \sum_{k=1}^{n}\left(\frac{1}{k}-\frac{1}{k+2}\right)=\frac{3}{2}\left(1+\frac{1}{2}-\frac{1}{n+1}-\frac{1}{n+2}\right) a .$$
When $n$ tends to infinity, the left-hand side tends to 1 while the right-hand side tends to $\frac{9}{4} a$. Therefore $a$ has to be at most $\frac{4}{9}$.

Hence the largest value of $a$ is $\frac{4}{9}$.

We shall give an alternative method to establish (1) with $a=\frac{4}{9}$. We define $y_{k}=x_{k}-x_{k-1}>0$ for $1 \leqslant k \leqslant n$. By the Cauchy-Schwarz Inequality, for $1 \leqslant k \leqslant n$, we have
$$\left(y_{1}+y_{2}+\cdots+y_{k}\right)\left(\sum_{j=1}^{k} \frac{1}{y_{j}}\binom{j+1}{2}^{2}\right) \geqslant\left(\binom{2}{2}+\binom{3}{2}+\cdots+\binom{k+1}{2}\right)^{2}=\binom{k+2}{3}^{2} .$$
This can be rewritten as
$$\frac{k+1}{y_{1}+y_{2}+\cdots+y_{k}} \leqslant \frac{36}{k^{2}(k+1)(k+2)^{2}}\left(\sum_{j=1}^{k} \frac{1}{y_{j}}\binom{j+1}{2}^{2}\right) \tag{3}$$
Summing (3) over $k=1,2, \ldots, n$, we get
$$\frac{2}{y_{1}}+\frac{3}{y_{1}+y_{2}}+\cdots+\frac{n+1}{y_{1}+y_{2}+\cdots+y_{n}} \leqslant \frac{c_{1}}{y_{1}}+\frac{c_{2}}{y_{2}}+\cdots+\frac{c_{n}}{y_{n}} \tag{4}$$
where for $1 \leqslant m \leqslant n$,
$$\begin{aligned} c_{m} & =36\binom{m+1}{2}^{2} \sum_{k=m}^{n} \frac{1}{k^{2}(k+1)(k+2)^{2}} \\ & =\frac{9 m^{2}(m+1)^{2}}{4} \sum_{k=m}^{n}\left(\frac{1}{k^{2}(k+1)^{2}}-\frac{1}{(k+1)^{2}(k+2)^{2}}\right) \\ & =\frac{9 m^{2}(m+1)^{2}}{4}\left(\frac{1}{m^{2}(m+1)^{2}}-\frac{1}{(n+1)^{2}(n+2)^{2}}\right)<\frac{9}{4} \end{aligned}$$
From (4), the inequality (1) holds for $a=\frac{4}{9}$. This is also the upper bound as can be verified in the same way as Solution 1.