2001 IMO Shortlist Problems/A2

Problem

Let $a_0, a_1, a_2, \ldots$ be an arbitrary infinite sequence of positive numbers. Show that the inequality $1 + a_n > a_{n - 1} \sqrt [n]{2}$ holds for infinitely many positive integers $n$.

Solution

We proceed with a proof by contradiction. Suppose the statement were false. Then, there exists a sequence $a_0, a_1, \ldots$ of positive integers for which there are only finitely many $a_n$ with $1+a_n> a_{n-1}\sqrt[n]{2}$. Let the largest such $n$ be $N-1$, so that $1+a_n\le a_{n-1}\sqrt[n]{2}$ whenever $n\le N-1$. Then, it is clear that $1+a_{n+N}\le a_{n+N-1}\sqrt[n]{2}$ for all nonnegative $n$. Therefore, define $b_n=a_{n+N}$. If there does not exist a sequence $b_0, b_1, \ldots$ of positive integers for which $1+b_n\le b_{n-1}\sqrt[n]{2}$, it is clear that there will not exist any sequence $a_0, a_1, \ldots$ for which that property is eventually true.

Thus, I claim there does not exist a sequence of positive integers $b_0, b_1, \ldots$ for which $1+b_n\le b_{n-1}\sqrt[n]{2}$. Again, suppose there does exist such a sequence. Then, define $x_0=b_0$ and $x_n=x_{n-1}\sqrt[n]{2} -1$. It is clear that $x_n\ge b_n$ for all $n$. I claim that this sequence will always become eventually negative. Note that $x_n=s_nx_{n-1}-1=s_n(s_{n-1}x_{n-2}-1)-1=\ldots=x_0s_n\cdot s_{n-1}\cdot\ldots\cdot s_0-\sum_{i=1}^{n-1}(\prod_{j=i}^n s_j)-1$, which becomes negative if and only if $\frac{x_n}{\prod_{i=1}^ns_i}=x_0-1-\frac{1}{s_1}-\frac{1}{s_1}{s_2}-\ldots$ does. In other words, $x_n$ becomes zero if $t_k=\sum_{i=1}^{k}\frac{1}{\prod_{j=1}^i s_j}$ is unbounded. However, $\sqrt[n]{2}$ is eventually less than $\frac{n+1}{n}$, so this sum is indeed unbounded and the proof is complete.

Resources