Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(Added a solution.)
m (→‎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.
+
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-1</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
 
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

Latest revision as of 04:38, 17 June 2019

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2001_IMO_Shortlist_Problems/A2&oldid=106468"