Romanian Mathematical Olympiad - District Round

We induct on $n$. The case $n=1$ is trivial. Suppose the claim holds for $n$ numbers. If $a_{n+1} \le 1$ then $\frac{a_{n+1}}{n+1} \le \frac{1}{n+1}$ and the conclusion follows. If $a_{n+1} > 1$, then $\frac{a_1}{1} + \dots + \frac{a_n}{n} + \frac{a_{n+1}}{n+1} \le \frac{a_1}{1} + \dots + \frac{a_n + a_{n+1} - 1}{n} + \frac{1}{n+1}$. Now apply the induction hypothesis to the following $n$ numbers $a_1, \dots, a_{n-1}, a_n + a_{n+1} - 1$ to get the claim.

Let $S_k = a_1 + a_2 + \dots + a_k$, $S_0 = 0$ and notice that $S_k - S_{k-1} = a_k$ for all $k = 1, 2, \dots, n$. Then $\sum_{k=1}^n \frac{a_k}{k} = \sum_{k=1}^n \frac{S_k - S_{k-1}}{k} = \sum_{k=1}^n \frac{S_k}{k(k+1)} \le \frac{1}{2} + \dots + \frac{1}{n}$, as claimed.