# 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.