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

Revision as of 20:15, 5 April 2015

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

@@ 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 ==

Page

Toolbox

Search

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

Revision as of 20:15, 5 April 2015

Problem

Solution

Resources