# Difference between revisions of "2001 IMO Shortlist Problems/A2"

m (New page: == Problem == Let <math>a_0, a_1, a_2, \ldots</math> be an arbitrary infinite sequence of positive numbers. Show that the inequality <math>1 + a_n > a_{n - 1} \sqrt [n]{2}</math> holds fo...) |
(Added a solution.) |
||

Line 3: | Line 3: | ||

== Solution == | == Solution == | ||

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

+ | |||

+ | Thus, I claim there does not exist a sequence of positive integers <math>b_0, b_1, \ldots</math> for which <math>1+b_n\le b_{n-1}\sqrt[n]{2}</math>. Again, suppose there does exist such a sequence. Then, define <math>x_0=b_0</math> and <math>x_n=x_{n-1}\sqrt[n]{2} -1</math>. It is clear that <math>x_n\ge b_n</math> for all <math>n</math>. I claim that this sequence will always become eventually negative. Note that | ||

+ | <math>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</math>, | ||

+ | which becomes negative if and only if <math>\frac{x_n}{\prod_{i=1}^ns_i}=x_0-1-\frac{1}{s_1}-\frac{1}{s_1}{s_2}-\ldots</math> does. In other words, <math>x_n</math> | ||

+ | becomes zero if <math>t_k=\sum_{i=1}^{k}\frac{1}{\prod_{j=1}^i s_j}</math> is unbounded. However, <math>\sqrt[n]{2}</math> is eventually less than <math>\frac{n+1}{n}</math>, so this sum is indeed unbounded and the proof is complete. | ||

== Resources == | == Resources == |

## Revision as of 20:15, 5 April 2015

## Problem

Let be an arbitrary infinite sequence of positive numbers. Show that the inequality holds for infinitely many positive integers .

## Solution

We proceed with a proof by contradiction. Suppose the statement were false. Then, there exists a sequence of positive integers for which there are only finitely many with . Let the largest such be , so that whenever . Then, it is clear that for all nonnegative . Therefore, define . If there does not exist a sequence of positive integers for which , it is clear that there will not exist any sequence for which that property is eventually true.

Thus, I claim there does not exist a sequence of positive integers for which . Again, suppose there does exist such a sequence. Then, define and . It is clear that for all . I claim that this sequence will always become eventually negative. Note that , which becomes negative if and only if does. In other words, becomes zero if is unbounded. However, is eventually less than , so this sum is indeed unbounded and the proof is complete.