Problem 5

Let

f

be an injective function from

\{1,2,3,\ldots\}

into itself. Prove that for any

n

we have

\sum_{k=1}^{n} f(k)k^{-2} \geq \sum_{k=1}^{n} k^{-1}

Step 3 of 4: Use distinctness

Previous step Next step

In plain words

Distinct positive integers cannot start below 1,2,...,n.

a_k^\uparrow\ge k\quad\Rightarrow\quad\sum_{k=1}^n\frac{a_k^\uparrow}{k^2}\ge\sum_{k=1}^n\frac{k}{k^2}

Detailed analysis

The increasing rearrangement $a_k^\uparrow$ consists of distinct positive integers, so its $k$ -th term is at least $k$ . Multiplying by the positive weight $1/k^2$ and summing gives the displayed bound.