An Increasing Sequence from 2014 IMO

Here's Problem 1 from the 2014 IMO:

Let $a_0 \lt a_1 \lt a_2 \ldots$ be an infinite sequence of positive integers.

Prove that there exists a unique integer $n\geq 1$ such that

$\displaystyle a_n \lt \frac{a_0+a_1+a_2+\cdots+a_n}{n} \leq a_{n+1}.$

Solution

Solution below is by Leo Giugiuc (communicated July 8, 2014).

For $n\ge 1,$ define $\displaystyle x_{n}=na_{n}-\sum_{i=0}^{n}a_{i},$ $x_{0}=-a_{0}.$

Sequence $\{x_{n}\}$ has the following properties:

$x_{0}\lt 0,$
$x_{n+1}-x_{n}=n(a_{n+1}-a_{n}),$ $n\ge 1.$

It follows that, like $\{a_{n}\},$ sequence $\{x_{n}\}$ is strictly increasing. Furthermore, for $n\ge 2,$

$\displaystyle x_{n} = -a_{0}+\sum_{i=1}^{n}(a_{n}-a_{0})\ge -a_{0}+\sum_{i=1}^{n}i=-a_{0}+\frac{n(n-1)}{2},$

implying that $\{x_{n}\}$ is unbounded. Hence, there is $n_{0}\ge 2$ such that, for $n\gt n_{0},$ $x_{n}\gt 0.$ Let $n_{1}$ be the least of all such $n_{0}.$ Define $k=n_{1}-1.$ Then $x_{k}\lt 0$ whereas $x_{k+1}\ge 0.$ This is equivalent to saying that

$\displaystyle a_k \lt \frac{a_0+a_1+a_2+\cdots+a_k}{k} \leq a_{k+1}.$

We thus found one required index. There is no other, for, if $n\ge k+1,$

$a_{n+1}\gt a_{n}\ge \displaystyle \frac{a_0+a_1+a_2+\cdots+a_n}{n};$

while, if $1\le n\lt k,$ then

$a_{n+1}\lt\displaystyle \frac{a_0+a_1+a_2+\cdots+a_n}{n}.$

71536280