An International Mathematical Olympiad Problem

July 12, 2015

I came across an International Mathematical Olympiad problem from 1978 which I had the feeling I would be able to solve quickly. The problem is stated as follows:

Problem (IMO ‘78)

Suppose that $n$ is a positive integer, and that $ (a _ k) $ is a one-one sequence of positive integers. Then \[ \sum _ {k=1} ^{n} \frac{1}{k} \leq \sum _ {k=1}^{n} \frac{a _ k} {k^2} \].

In order to prove this fact I will use two elementary inequalities.

Lemma (Cauchy-Schwarz inequality)

Suppose that $ (a _ k), (b _ k) $ are sequences of real numbers. Then for any positive integer $ n$ we have

\[ \sum _ {k=1} ^ {n} a _ k b _ k \leq \sqrt{\sum _ {k=1} ^ {n} a _ k ^2 } \sqrt{\sum _ {k=1} ^{n} b _ k ^2 } \]

Lemma (Young’s inequality)

Suppose that $ a,b $ are real numbers. Then

\[ ab \leq \frac{1}{2}a^2 + \frac{1}{2} b^2 \]

Proof of main fact

We have

$$ \begin{aligned} \sum_{k=1}^{n} \frac{1}{k} &= \sum_{k=1}^{n}\frac{\sqrt{a_k}}{\sqrt{a_k}k} \\ &\leq \sqrt{\sum_{k=1}^{n}\frac{1}{a_k}}\sqrt{\sum_{k=1}^{n}\frac{a_k}{k^2}} \\ &\leq \frac{1}{2}\sum_{k=1}^{n}\frac{1}{a_k} + \frac{1}{2}\sum_{k=1}^n \frac{a_k}{k^2} \\ &\leq \frac{1}{2}\sum_{k=1}^{n}\frac{1}{k} + \frac{1}{2}\sum_{k=1}^n \frac{a_k}{k^2} \end{aligned} $$

completing the proof. Note that the last inequality is where I used the fact that the sequence $ (a _ k) $ was a one-one sequence of positive integers.