NMO Selection Tests for the Junior Balkan Mathematical Olympiad

The number $a_k$ of the multiples of $k$ in the set $\{1,2,\dots ,n\}$ is $\lfloor \frac{n}{k}\rfloor$. Let us count the appearances of the term $\frac{1}{i}$ in the sum $x_1+x_2+\cdots +x_n$. The term $\frac{1}{i}$ belongs in the sum $x_k=\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{a_k}$ if and only if $i\le a_k=\lfloor \frac{n}{k}\rfloor$.

Fix $i=1,2,\dots ,n$ and denote by $m=m(i)$ the index of the last sum $x_m$ containing $\frac{1}{i}$. Then $i\le \lfloor \frac{n}{m}\rfloor \le \frac{n}{m}$, i.e. $m\le \frac{n}{i}$.

Remember $\frac{1}{i}$ belongs to the sums $x_1,x_2,\dots ,x_m$ and those only, therefore one has $$x_1+x_2+\cdots +x_n=\sum _{i=1}^n\frac{1}{i}m(i)\le \sum _{i=1}^n\frac{1}{i}\cdot \frac{n}{i}=n\sum _{i=1}^n\frac{1}{i^2}.$$ The conclusion immediately ensues.