# Prove that $\sum_{i = 1}^n \frac{x_i}{i^2} \geq \sum_{i = 1}^n \frac{1}{i}.$

Let $x_1,x_2,\ldots,x_n$ be distinct positive integers. Prove that $$\displaystyle \sum_{i = 1}^n \dfrac{x_i}{i^2} \geq \sum_{i = 1}^n \dfrac{1}{i}.$$

Attempt

I tried using Cauchy-Schwarz and I got that $$(x_1^2+x_2^2+\cdots+x_n^2) \left (\dfrac{1}{1^2}+\dfrac{1}{2^2}+\cdots+ \dfrac{1}{n^2} \right ) \geq \left ( \dfrac{x_1}{1}+\dfrac{x_2}{2}+\cdots+\dfrac{x_n}{n} \right)^2 = \displaystyle \left (\sum_{i = 1}^n \dfrac{x_i}{i} \right)^2,$$ but this doesn't seem to help.

Let $0 < y_1 < y_2 < \ldots < y_n$ be an rearrangement of $x_1, x_2, \ldots x_n$ sorted in ascending order.

Since $y_k$ are distinct positive integers, one can show $y_k \ge k$ for $k = 1,\ldots, n$ by induction.

Since the finite sequence $\frac{1}{1^2}, \frac{1}{2^2}, \ldots, \frac{1}{n^2}$ is ascending, by rearrangement inequality, we have

$$\sum_{k=1}^n \frac{x_k}{k^2} \ge \sum_{k=1}^n \frac{y_k}{k^2} \ge \sum_{k=1}^n \frac{k}{k^2} = \sum_{k=1}^n \frac{1}{k}$$

A proof sketch that doesn't use the rearrangement inequality:

Since the integers are distinct it's enough to prove the claim in the case $\{x_1,\dots,x_n\}$ is a permutation on $\{1,\dots,n\}$. For positive integers $\alpha<\beta$, $\gamma < \delta$ you can show $$\alpha/\gamma + \beta/\delta < \beta/\gamma + \alpha/\delta$$ From here you can actually choose $\{x_1,\dots,x_n\}$ such that a lower bound on $\sum_{i=1}^n \frac{x_i}{n}$ is attained and from this you'll get the inequality.

Hint: Suppose $0<a<b$ and $0<x<y.$ Then $a/x + b/y < b/x + a/y.$