Home > Algebra, IMO, Olympiad, Problem Solving > Weird sequence

## Weird sequence

Suppose the sequence $(a_n)_n$ is given by $a_0,a_1 \geq 0$ and $a_n=|a_{n+1}-a_{n+2}|$. Prove that the sequence is bounded if and only if it consists only of two values, one of which is $0$.
IMO Shortlist 2004, various Team Selection Tests

Some solutions, or even formulations of the problem say that the sequence is bounded if and only if the function $f(n,k)=a_na_k(a_n-a_k)$ is identically zero on $\Bbb{N} \times \Bbb{N}$. This is obviously true if and only if the sequence assumes at most two values, one of them zero.

First, notice that if we have one zero term, or two consecutive equal terms, the sequence is uniquely defined, and has the desired property. Therefore, we assume the contrary here, that the sequence is bounded, never zero, and two consecutive terms are always different.

First prove that the sequence cannot get arbitrarily small. If it would, then some $a_i$ will be the smallest term until $i$. Then $a_{i-1}>a_i$ and $a_{i-2}=a_{i-1}-a_i<3$ and the smallest value of the sequence is among $a_0,a_1,a_2$, which means the sequence is bounded below by a positive (non-zero) constant. One proof can be given using the sequence $b_n=\max \{a_n,a_{n+1},a_{n+2}\}$, which can be easily be shown to be increasing. If $a_n$ is bounded, then so is $b_n$. Bounded and increasing means convergent. Analyzing $b_{n+1}-b_n$(which converges to zero) we see that it can be only zero or some $a_i>c>0$. Therefore, $b_n$ is eventually constant. From here it is quite easy to find a zero term for the sequence, which is a contradiction.

For more details or solutions see the following discussions on AoPS:

http://www.artofproblemsolving.com/Forum/viewtopic.php?t=83712