# Rearrangement and Cauchy

Let $a_1, \ldots, a_n$ be distinct positive integers. I want to prove that

$$\frac{a_1}{1^2} + \frac{a_2}{2^2} + \cdots + \frac{a_n}{n^2} \geq \frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{n}.$$

I've been considering using Rearrangement and Cauchy Schwarz, but cannot make any progress

## 2 Answers

Use the following: If $a_1, \ldots, a_n$ are distinct positive integers, then we can sort them according to their size $a_{n_1} \leq a_{n_2} \leq \ldots \leq a_{n_n}$ and get $$k \leq a_{n_k} ~ \forall k = 1, \ldots, n.$$

Hence, using Cauchy Schwarz, we compute

\begin{align*} \left( \sum_{k=1}^n \frac{1}{k} \right)^2 & = \left( \sum_{k=1}^n \frac{\sqrt{a_k}}{k} \cdot \frac{1}{\sqrt{a_k}}\right)^2 \leq \left( \sum_{k=1}^n \frac{a_k}{k^2} \right) \cdot \left( \sum_{k=1}^n \frac{1}{a_k} \right) = \left( \sum_{k=1}^n \frac{a_k}{k^2} \right) \cdot \left( \sum_{k=1}^n \frac{1}{a_{n_k}} \right)\\ & \leq \left( \sum_{k=1}^n \frac{a_k}{k^2} \right) \cdot \left( \sum_{k=1}^n \frac{1}{k} \right) \end{align*} Thus, dividing the inequality by $\sum_{k=1}^n 1/k$ yields $$\frac{1}{1} + \ldots + \frac{1}{n} = \sum_{k=1}^n \frac{1}{k} \leq \sum_{k=1}^n \frac{a_k}{k^2} = \frac{a_1}{1^2} + \ldots + \frac{a_n}{n^2}$$

First we quote (part of) the Rearrangement Inequality, in the notation used by Wikipedia: $$x_ny_1 + \cdots + x_1y_n \le x_{\sigma (1)}y_1 + \cdots + x_{\sigma (n)}y_n\tag{1}$$ for every choice of real numbers $$x_1\le\cdots\le x_n\quad\text{and}\quad y_1\le\cdots\le y_n,$$ and every permutation $$x_{\sigma(1)},\dots,x_{\sigma(n)}\,$$

We can assume that the $a_i$ are a permutation of $\{1,2,\dots,n\}$. For if that is not the case, and we replace the smallest of the $a_i$ by $1$, the second smallest by $2$, and so on, we weaken the inequality.

We want to prove that $$\frac{a_n}{n^2}+\frac{a_{n-1}}{(n-1)^2}+\cdots +\frac{a_1}{1^2}\ge \frac{1}{n}+\frac{1}{n-1}+\cdot +\frac{1}{1}.\tag{2}$$ Let $y_i=\frac{1}{(n+1-i)^2}$ and let $x_i=i$. Then the Rearrangement Inequality (1) directly gives (2).