MathLabs

Problem 5

Let ff be an injective function from {1,2,3,…}\{1,2,3,\ldots\} into itself. Prove that for any nn we have ∑k=1nf(k)k−2≥∑k=1nk−1\sum_{k=1}^{n} f(k)k^{-2} \geq \sum_{k=1}^{n} k^{-1}.
Step 2 of 4: Sort the values increasingly
Previous stepNext step
In plain words

Descending weights prefer small numbers first.

∑k=1nakk2≥∑k=1nak↑k2\sum_{k=1}^n\frac{a_k}{k^2}\ge\sum_{k=1}^n\frac{a_k^\uparrow}{k^2}
Detailed analysis

The weights 1,1/4,…,1/n21,1/4,\ldots,1/n^2 decrease with kk. The rearrangement inequality says pairing the smallest values with the largest weights minimizes the sum, so sorting aka_k increasingly can only decrease it.