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 "2004 IMO Shortlist Problems/A2"

 
(+ solution, weaker result)
 
Line 4: Line 4:
 
An infinite sequence <math> a_0, a_1, a_2, \ldots </math> of real numbers satisfies the condition
 
An infinite sequence <math> a_0, a_1, a_2, \ldots </math> of real numbers satisfies the condition
 
<center>
 
<center>
−
<math> \displaystyle a_n = | a_{n+1} - a_{n+2} | \qquad </math> for every <math> n \ge 0 </math>,
+
<math>a_n = | a_{n+1} - a_{n+2} | \qquad </math> for every <math> n \ge 0 </math>,
 
</center>
 
</center>
−
with <math> \displaystyle a_0 </math> and <math> \displaystyle a_1 </math> positive and distinct.  Can this sequence be bounded?
+
with <math>a_0 </math> and <math>a_1 </math> positive and distinct.  Can this sequence be bounded?
  
 
''This was also Problem 4 of the 2005 German Pre-[[TST]] and Problem 1 of the first 2005 black [[MOP]] test.  It was Problem 3, Day 2 of the 2005 Romanian TST in the following form:''
 
''This was also Problem 4 of the 2005 German Pre-[[TST]] and Problem 1 of the first 2005 black [[MOP]] test.  It was Problem 3, Day 2 of the 2005 Romanian TST in the following form:''
  
−
A sequence of real numbers <math> \displaystyle \{a_n\}_n </math> is called a ''bs'' sequence if <math> \displaystyle a_n = |a_{n+1} - a_{n+2}| </math>, for all <math> \displaystyle n\geq 0 </math>. Prove that a bs sequence is bounded if and only if the function <math> \displaystyle f </math> given by <math> \displaystyle f(n,k)=a_na_k(a_n-a_k) </math>, for all <math> \displaystyle n,k\geq 0 </math> is the null function.
+
A sequence of real numbers <math>\{a_n\}_n </math> is called a ''bs'' sequence if <math>a_n = |a_{n+1} - a_{n+2}| </math>, for all <math>n\geq 0 </math>. Prove that a bs sequence is bounded if and only if the function <math>f </math> given by <math>f(n,k)=a_na_k(a_n-a_k) </math>, for all <math>n,k\geq 0 </math> is the null function.
  
 +
__TOC__
 
== Solution ==
 
== Solution ==
−
 
+
=== Solution 1 ===
−
We note that each of the <math> \displaystyle a_i </math> must be nonnegative.
+
We note that each of the <math>a_i </math> must be nonnegative.
  
 
'''Lemma 1.''' If the two initial terms of the sequence are nonzero and distinct, then every term of the sequence is nonzero and no two consecutive terms are equal.
 
'''Lemma 1.''' If the two initial terms of the sequence are nonzero and distinct, then every term of the sequence is nonzero and no two consecutive terms are equal.
Line 21: Line 22:
  
 
Consider a sequence <math> \{b_i\}_{i=0}^{\infty} </math> of positive reals which obeys the recursive relation
 
Consider a sequence <math> \{b_i\}_{i=0}^{\infty} </math> of positive reals which obeys the recursive relation
−
<center> <math> \displaystyle b_{n+2} = |b_{n+1} - b_n | </math>. </center>
+
<center> <math>b_{n+2} = |b_{n+1} - b_n | </math>. </center>
  
 
'''Lemma 2.''' <math> \min (b_i, b_{i+1}, b_{i+2}) \ge \min (b_{i+3}, b_{i+4}, b_{i+5}) </math>.
 
'''Lemma 2.''' <math> \min (b_i, b_{i+1}, b_{i+2}) \ge \min (b_{i+3}, b_{i+4}, b_{i+5}) </math>.
  
−
''Proof.''  We note that if <math> \displaystyle b_k \le b_{k+1} </math>, then <math> \displaystyle b_{k+2} = b_{k+1} - b_k </math> and <math> \displaystyle b_{k+3} = b_k </math>.  Thus if <math> \displaystyle b_{i+3}, b_{i+4}, b_{i+5} > \min(b_i, b_{i+1}, b_{i+2}) </math>, we must have <math> \displaystyle b_i, b_{i+1} > b_{i+2} > b_{i+3} </math>, a contradiction.
+
''Proof.''  We note that if <math>b_k \le b_{k+1} </math>, then <math>b_{k+2} = b_{k+1} - b_k </math> and <math>b_{k+3} = b_k </math>.  Thus if <math>b_{i+3}, b_{i+4}, b_{i+5} > \min(b_i, b_{i+1}, b_{i+2}) </math>, we must have <math>b_i, b_{i+1} > b_{i+2} > b_{i+3} </math>, a contradiction.
  
 
'''Lemma 3.''' Let <math> r = \left\lfloor \frac{b_{k-1}}{b_k} \right\rfloor </math>, <math> j = \left\lceil \frac{3}{2}r \right\rceil </math>.  Then <math> \min (b_{k+j},b_{k+j+1},b_{k+j+2}) \le \frac{1}{2}b_{k+1} </math>.
 
'''Lemma 3.''' Let <math> r = \left\lfloor \frac{b_{k-1}}{b_k} \right\rfloor </math>, <math> j = \left\lceil \frac{3}{2}r \right\rceil </math>.  Then <math> \min (b_{k+j},b_{k+j+1},b_{k+j+2}) \le \frac{1}{2}b_{k+1} </math>.
  
−
''Proof.''  For <math> 2i+2 \le r </math>, easy induction yields <math> \displaystyle b_{k+3i} = b_k </math>, <math> \displaystyle b_{k+3i+1} = b_{k-1} - (2i+1)b_k </math>, <math> \displaystyle b_{k+3i+2} = b_{k-1} - (2i+2)b_k </math>.
+
''Proof.''  For <math> 2i+2 \le r </math>, easy induction yields <math>b_{k+3i} = b_k </math>, <math>b_{k+3i+1} = b_{k-1} - (2i+1)b_k </math>, <math>b_{k+3i+2} = b_{k-1} - (2i+2)b_k </math>.
 +
 
 +
Now, if <math>r </math> is even, we have <math>b_{k+3r/2 - 1} = b_{k-1} - b_kr </math>, which is less than <math>b_k </math> by the definition of <math>r </math>, and <math>b_{k+3r/2} = b_k </math>, <math>b_{k+3r/2 +1} = b_{3r/2} - b_{k+3r/2-1} </math>, <math>b_{k+3r/2+2} = b_{k+3r/2} </math>.  Since <math>b_{k+3r/2+1} </math> and <math>b_{k+3r/2+2} </math> add to <math>b_{3r/2} = b_k </math>, one of them must be at most <math> \frac{b_k}{2} </math>, and the lemma follows.
 +
 
 +
On the other hand, if <math>r </math> is odd, then set <math>s = r-1 </math> and we have <math>b_{k+3s/2+1} = b_{k-1} - b_kr < b_k </math>, <math>b_{k+3s/2 + 2} = b_k </math>, and <math>b_{k+3s/2+3} = b_{k+3s/2 + 2} - b_{k+3s/2+1} </math>, so as before, at least one of <math>b_{k+3s/2+1} </math>, <math>b_{k+3s/2+3} </math> must be at most <math> \frac{b_k}{2} </math>.  In fact, we have <math>{} b_{k+3s/2+4}= b_{k+3s/2+1} </math>, so the minimum of <math>b_{k+3s/2+3}, b_{k+3s/2+4} </math> is at most <math>\frac{b_k}{2} </math>, upholding the lemma, since in this case <math> \left\lceil \frac{3}{2}r \right\rceil = \frac{3}{2}s+2 </math>.
 +
 
  
−
Now, if <math> \displaystyle r </math> is even, we have <math> \displaystyle b_{k+3r/2 - 1} = b_{k-1} - b_kr </math>, which is less than <math> \displaystyle b_k </math> by the definition of <math> \displaystyle r </math>, and <math> \displaystyle b_{k+3r/2} = b_k </math>, <math> \displaystyle b_{k+3r/2 +1} = b_{3r/2} - b_{k+3r/2-1} </math>, <math> \displaystyle b_{k+3r/2+2} = b_{k+3r/2} </math>.  Since <math> \displaystyle b_{k+3r/2+1} </math> and <math> \displaystyle b_{k+3r/2+2} </math> add to <math> \displaystyle b_{3r/2} = b_k </math>, one of them must be at most <math> \frac{b_k}{2} </math>, and the lemma follows.
+
Now, suppose that <math>\{ a_i \}_{i=0}^{\infty} </math> is bounded, i.e., there exists some real <math>N </math> greater than each <math>a_i </math>.  By setting <math>b_1, b_0 </math> equal to <math>a_{n-1}, a_n </math>, we generate the first <math>n </math> of the <math>a_i </math> in reverse, and from Lemma 2, we can see that <math>m = \min (a_1,a_2,a_3) </math> is a lower bound of the <math>a_i </math>.  But by making <math>n </math> greater than <math> \lceil \log_2 (N/m) +1 \rceil \left\lceil \frac{3}{2} \left\lfloor \frac{N}{m} \right\rfloor \right\rceil </math>, by applying Lemma 3, we obtain the result <math>m \le \frac{1}{2} m </math>, which is a contradiction when <math>a_0, a_1 </math> are distinct and greater than 0, by Lemma 1.
  
−
On the other hand, if <math> \displaystyle r </math> is odd, then set <math> \displaystyle s = r-1 </math> and we have <math> \displaystyle b_{k+3s/2+1} = b_{k-1} - b_kr < b_k </math>, <math> \displaystyle b_{k+3s/2 + 2} = b_k </math>, and <math> \displaystyle b_{k+3s/2+3} = b_{k+3s/2 + 2} - b_{k+3s/2+1} </math>, so as before, at least one of <math> \displaystyle b_{k+3s/2+1} </math>, <math> \displaystyle b_{k+3s/2+3} </math> must be at most <math> \frac{b_k}{2} </math>.  In fact, we have <math> \displaystyle {} b_{k+3s/2+4}= b_{k+3s/2+1} </math>, so the minimum of <math> \displaystyle b_{k+3s/2+3}, b_{k+3s/2+4} </math> is at most <math>\frac{b_k}{2} </math>, upholding the lemma, since in this case <math> \left\lceil \frac{3}{2}r \right\rceil = \frac{3}{2}s+2 </math>.
+
Now, if <math>a_na_k(a_n-a_k) = 0 </math> for all natural <math>n </math>, all the nonzero <math>a_i </math> must be equal and the sequence is bounded.  On the other hand, if <math>a_{n+1}a_n(a_{n+1}-a_n) = 0 </math> always holds, then either <math>a_{n+1} = a_n </math> and <math> a_{n+2} = 0 </math>, or one of <math>a_{n+1}, a_{n} </math> is equal to zero and <math>a_{n+2} </math> is equal to the other one; hence by induction, all the nonzero terms of the sequence are equal, and <math>a_na_k(a_n-a_k) </math> is always equal to zero.  Hence if for some <math>n, k </math>, <math>{} a_na_k(a_n-a_k) \neq 0 </math>, then there exist two distinct positive consecutive terms of sequence, which is then unbounded as proven above.
  
−
Now, suppose that <math>\{ a_i \}_{i=0}^{\infty} </math> is bounded, i.e., there exists some real <math> \displaystyle N </math> greater than each <math> \displaystyle a_i </math>.  By setting <math> \displaystyle b_1, b_0 </math> equal to <math> \displaystyle a_{n-1}, a_n </math>, we generate the first <math> \displaystyle n </math> of the <math> \displaystyle a_i </math> in reverse, and from Lemma 2, we can see that <math> \displaystyle m = \min (a_1,a_2,a_3) </math> is a lower bound of the <math> \displaystyle a_i </math>. But by making <math> \displaystyle n </math> greater than <math> \lceil \log_2 (N/m) +1 \rceil \left\lceil \frac{3}{2} \left\lfloor \frac{N}{m} \right\rfloor \right\rceil </math>, by applying Lemma 3, we obtain the result <math> \displaystyle m \le \frac{1}{2} m </math>, which is a contradiction when <math> \displaystyle a_0, a_1 </math> are distinct and greater than 0, by Lemma 1.
+
=== Solution 2 ===
 +
The given recursive condition is equivalent to <math>a_{n+2} = a_{n+1} + a_n</math> if <math>a_{n+1} < a_n</math>, and <math>a_{n+2} = a_{n+1} \pm a_n</math> otherwise. Note that if <math>a_{n+1} > a_n</math>, then <math>a_{n+1} = a_n + a_{n-1}</math>.  
  
−
Now, if <math> \displaystyle a_na_k(a_n-a_k) = 0 </math> for all natural <math> \displaystyle n </math>, all the nonzero <math> \displaystyle a_i </math> must be equal and the sequence is bounded.  On the other hand, if <math> \displaystyle a_{n+1}a_n(a_{n+1}-a_n) = 0 </math> always holds, then either <math> \displaystyle a_{n+1} = a_n </math> and <math> a_{n+2} = 0 </math>, or one of <math> \displaystyle a_{n+1}, a_{n} </math> is equal to zero and <math> \displaystyle a_{n+2} </math> is equal to the other one; hence by induction, all the nonzero terms of the sequence are equal, and <math> \displaystyle a_na_k(a_n-a_k) </math> is always equal to zero.  Hence if for some <math> \displaystyle n, k </math>, <math>{} a_na_k(a_n-a_k) \neq 0 </math>, then there exist two distinct positive consecutive terms of sequence, which is then unbounded as proven above.
+
'''Lemma 1: ''' Let <math>m > 0</math> be the minimal element of <math>\{a_n\}</math>. Then <math>m = \text{min}\,(a_0,a_1,a_2)</math>.
  
 +
''Proof: '' Suppose <math>k \ge 3</math> is the minimal value of <math>k</math> such that <math>m = a_k</math>. Then <math>a_k = a_{k-1} - a_{k-2} \Longrightarrow a_{k-1} > a_{k-2}</math>, so <math>a_{k-1} = a_{k-2} + a_{k-3}</math>, and <math>a_k = a_{k-3}</math>. This contradicts our assumption of minimality.
 +
 +
Let <math>T_n = a_n + a_{n+1} + a_{n+2}</math>; we claim that <math>T_{n+2} > T_n + m</math>, which would imply that <math>T_n</math> is unbounded, in turn implying that <math>a_n</math> is unbounded.
 +
 +
*Suppose <math>a_{n+2} = a_n + a_{n+1}</math>; then <math>a_{n+3} = a_{n+2} - a_{n+1} = a_n</math> or <math>a_{n+3} = a_{n+2} + a_{n+1}</math>. In the former case, <math>a_{n+3} < a_{n+2}</math> so <math>a_{n+4} = a_{n+3} + a_{n+2} = a_n + a_{n+2}</math>, and <math>T_{n+2} = (a_{n+2}) + (a_{n}) + (a_{n} + a_{n+2}) = T_n + 2a_n > T_n + m</math>. In the latter case, <math>T_{n+2} > a_{n+2} + a_{n+3} + m > T_n + a_{n+1} + m</math>.
 +
*Suppose <math>a_{n+1} > a_n</math>, <math>a_{n+2} = a_{n+1} - a_n</math>; then <math>a_{n+3} = a_{n+2} + a_{n+1}</math>, and <math>a_{n+4} \ge a_{n+3} - a_{n+2} = a_{n+1}</math>. Then <math>T_{n+2} = a_{n+4} + a_{n+3} + a_{n+2} \ge (a_{n+1}) + (a_{n+2} + a_{n+1}) + a_{n+2} > T_n + a_{n+2} \ge T_n + m</math>.
 +
 +
Then <math>T_{n+2k} > T_n + mk</math>, so <math>T_{n}</math> is unbounded, as desired.
  
 
{{alternate solutions}}
 
{{alternate solutions}}
  
−
 
+
== See also ==
−
'''Comment by the proposer.'''  The following statements are equivalent for a sequence <math> a_0, a_1, \ldots, a_n, \ldots </math> of real numbers satisfying <math> \displaystyle a_n = |a_{n+1} - a_{n+2}| </math> for <math> n \ge 0 </math>: <br>
+
'''Comment by the proposer.'''  The following statements are equivalent for a sequence <math> a_0, a_1, \ldots, a_n, \ldots </math> of real numbers satisfying <math>a_n = |a_{n+1} - a_{n+2}| </math> for <math> n \ge 0 </math>: <br>
 
i) the sequence is bounded; <br>
 
i) the sequence is bounded; <br>
−
ii) the function <math> \displaystyle f </math> defined by <math> \displaystyle f(n,k) = a_na_k(a_n-a_k) </math>, for <math> n,k \ge 0 </math>, is identically zero; <br>
+
ii) the function <math>f </math> defined by <math>f(n,k) = a_na_k(a_n-a_k) </math>, for <math> n,k \ge 0 </math>, is identically zero; <br>
 
iii) the sequence is of the form <math> \ldots, 0,a,a,0,a,a,0,a,a, \ldots </math> with <math> a \ge 0 </math>.
 
iii) the sequence is of the form <math> \ldots, 0,a,a,0,a,a,0,a,a, \ldots </math> with <math> a \ge 0 </math>.
−
 
−
 
−
== Resources ==
 
  
 
* [[2004 IMO Shortlist Problems]]
 
* [[2004 IMO Shortlist Problems]]
Line 56: Line 68:
 
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=152740#p152740 Discussion on AoPS/MathLinks]
 
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=152740#p152740 Discussion on AoPS/MathLinks]
 
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=198930#198930 Further discussion on AoPS/MathLinks]
 
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=198930#198930 Further discussion on AoPS/MathLinks]
−
 
  
 
[[Category:Olympiad Algebra Problems]]
 
[[Category:Olympiad Algebra Problems]]

Latest revision as of 16:51, 28 November 2008

Problem

(Mihai Bălună, Romania) An infinite sequence $a_0, a_1, a_2, \ldots$ of real numbers satisfies the condition

$a_n = | a_{n+1} - a_{n+2} | \qquad$ for every $n \ge 0$,

with $a_0$ and $a_1$ positive and distinct. Can this sequence be bounded?

This was also Problem 4 of the 2005 German Pre-TST and Problem 1 of the first 2005 black MOP test. It was Problem 3, Day 2 of the 2005 Romanian TST in the following form:

A sequence of real numbers $\{a_n\}_n$ is called a bs sequence if $a_n = |a_{n+1} - a_{n+2}|$, for all $n\geq 0$. Prove that a bs sequence is bounded if and only if the function $f$ given by $f(n,k)=a_na_k(a_n-a_k)$, for all $n,k\geq 0$ is the null function.

Solution

Solution 1

We note that each of the $a_i$ must be nonnegative.

Lemma 1. If the two initial terms of the sequence are nonzero and distinct, then every term of the sequence is nonzero and no two consecutive terms are equal.

Proof. We proceed by induction; we are given a base case. If ${}a_k \neq a_{k+1}$, then $| a_{k+1} - a_{k+2} | \neq a_{k+1}$, so $a_{k+2} \neq 0$. Furthermore, since $|a_{k+1} - a_{k+2}| = a_k \neq 0$, $a_{k+1} \neq a_{k+2}$.

Consider a sequence $\{b_i\}_{i=0}^{\infty}$ of positive reals which obeys the recursive relation

$b_{n+2} = |b_{n+1} - b_n |$.

Lemma 2. $\min (b_i, b_{i+1}, b_{i+2}) \ge \min (b_{i+3}, b_{i+4}, b_{i+5})$.

Proof. We note that if $b_k \le b_{k+1}$, then $b_{k+2} = b_{k+1} - b_k$ and $b_{k+3} = b_k$. Thus if $b_{i+3}, b_{i+4}, b_{i+5} > \min(b_i, b_{i+1}, b_{i+2})$, we must have $b_i, b_{i+1} > b_{i+2} > b_{i+3}$, a contradiction.

Lemma 3. Let $r = \left\lfloor \frac{b_{k-1}}{b_k} \right\rfloor$, $j = \left\lceil \frac{3}{2}r \right\rceil$. Then $\min (b_{k+j},b_{k+j+1},b_{k+j+2}) \le \frac{1}{2}b_{k+1}$.

Proof. For $2i+2 \le r$, easy induction yields $b_{k+3i} = b_k$, $b_{k+3i+1} = b_{k-1} - (2i+1)b_k$, $b_{k+3i+2} = b_{k-1} - (2i+2)b_k$.

Now, if $r$ is even, we have $b_{k+3r/2 - 1} = b_{k-1} - b_kr$, which is less than $b_k$ by the definition of $r$, and $b_{k+3r/2} = b_k$, $b_{k+3r/2 +1} = b_{3r/2} - b_{k+3r/2-1}$, $b_{k+3r/2+2} = b_{k+3r/2}$. Since $b_{k+3r/2+1}$ and $b_{k+3r/2+2}$ add to $b_{3r/2} = b_k$, one of them must be at most $\frac{b_k}{2}$, and the lemma follows.

On the other hand, if $r$ is odd, then set $s = r-1$ and we have $b_{k+3s/2+1} = b_{k-1} - b_kr < b_k$, $b_{k+3s/2 + 2} = b_k$, and $b_{k+3s/2+3} = b_{k+3s/2 + 2} - b_{k+3s/2+1}$, so as before, at least one of $b_{k+3s/2+1}$, $b_{k+3s/2+3}$ must be at most $\frac{b_k}{2}$. In fact, we have ${} b_{k+3s/2+4}= b_{k+3s/2+1}$, so the minimum of $b_{k+3s/2+3}, b_{k+3s/2+4}$ is at most $\frac{b_k}{2}$, upholding the lemma, since in this case $\left\lceil \frac{3}{2}r \right\rceil = \frac{3}{2}s+2$.


Now, suppose that $\{ a_i \}_{i=0}^{\infty}$ is bounded, i.e., there exists some real $N$ greater than each $a_i$. By setting $b_1, b_0$ equal to $a_{n-1}, a_n$, we generate the first $n$ of the $a_i$ in reverse, and from Lemma 2, we can see that $m = \min (a_1,a_2,a_3)$ is a lower bound of the $a_i$. But by making $n$ greater than $\lceil \log_2 (N/m) +1 \rceil \left\lceil \frac{3}{2} \left\lfloor \frac{N}{m} \right\rfloor \right\rceil$, by applying Lemma 3, we obtain the result $m \le \frac{1}{2} m$, which is a contradiction when $a_0, a_1$ are distinct and greater than 0, by Lemma 1.

Now, if $a_na_k(a_n-a_k) = 0$ for all natural $n$, all the nonzero $a_i$ must be equal and the sequence is bounded. On the other hand, if $a_{n+1}a_n(a_{n+1}-a_n) = 0$ always holds, then either $a_{n+1} = a_n$ and $a_{n+2} = 0$, or one of $a_{n+1}, a_{n}$ is equal to zero and $a_{n+2}$ is equal to the other one; hence by induction, all the nonzero terms of the sequence are equal, and $a_na_k(a_n-a_k)$ is always equal to zero. Hence if for some $n, k$, ${} a_na_k(a_n-a_k) \neq 0$, then there exist two distinct positive consecutive terms of sequence, which is then unbounded as proven above.

Solution 2

The given recursive condition is equivalent to $a_{n+2} = a_{n+1} + a_n$ if $a_{n+1} < a_n$, and $a_{n+2} = a_{n+1} \pm a_n$ otherwise. Note that if $a_{n+1} > a_n$, then $a_{n+1} = a_n + a_{n-1}$.

Lemma 1: Let $m > 0$ be the minimal element of $\{a_n\}$. Then $m = \text{min}\,(a_0,a_1,a_2)$.

Proof: Suppose $k \ge 3$ is the minimal value of $k$ such that $m = a_k$. Then $a_k = a_{k-1} - a_{k-2} \Longrightarrow a_{k-1} > a_{k-2}$, so $a_{k-1} = a_{k-2} + a_{k-3}$, and $a_k = a_{k-3}$. This contradicts our assumption of minimality.

Let $T_n = a_n + a_{n+1} + a_{n+2}$; we claim that $T_{n+2} > T_n + m$, which would imply that $T_n$ is unbounded, in turn implying that $a_n$ is unbounded.

  • Suppose $a_{n+2} = a_n + a_{n+1}$; then $a_{n+3} = a_{n+2} - a_{n+1} = a_n$ or $a_{n+3} = a_{n+2} + a_{n+1}$. In the former case, $a_{n+3} < a_{n+2}$ so $a_{n+4} = a_{n+3} + a_{n+2} = a_n + a_{n+2}$, and $T_{n+2} = (a_{n+2}) + (a_{n}) + (a_{n} + a_{n+2}) = T_n + 2a_n > T_n + m$. In the latter case, $T_{n+2} > a_{n+2} + a_{n+3} + m > T_n + a_{n+1} + m$.
  • Suppose $a_{n+1} > a_n$, $a_{n+2} = a_{n+1} - a_n$; then $a_{n+3} = a_{n+2} + a_{n+1}$, and $a_{n+4} \ge a_{n+3} - a_{n+2} = a_{n+1}$. Then $T_{n+2} = a_{n+4} + a_{n+3} + a_{n+2} \ge (a_{n+1}) + (a_{n+2} + a_{n+1}) + a_{n+2} > T_n + a_{n+2} \ge T_n + m$.

Then $T_{n+2k} > T_n + mk$, so $T_{n}$ is unbounded, as desired.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See also

Comment by the proposer. The following statements are equivalent for a sequence $a_0, a_1, \ldots, a_n, \ldots$ of real numbers satisfying $a_n = |a_{n+1} - a_{n+2}|$ for $n \ge 0$:
i) the sequence is bounded;
ii) the function $f$ defined by $f(n,k) = a_na_k(a_n-a_k)$, for $n,k \ge 0$, is identically zero;
iii) the sequence is of the form $\ldots, 0,a,a,0,a,a,0,a,a, \ldots$ with $a \ge 0$.

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