2004 IMO Shortlist Problems/A2

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