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 4 of 4: Conclude the inequality
Previous stepNext step
In plain words

The minimum is achieved by the identity arrangement.

∑k=1nf(k)k2≥∑k=1nkk2=∑k=1n1k\sum_{k=1}^n\frac{f(k)}{k^2}\ge\sum_{k=1}^n\frac{k}{k^2}=\sum_{k=1}^n\frac1k
Detailed analysis

Combining the rearrangement step with ak=f(k)a_k=f(k) gives exactly the required inequality.