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:




Categories: Algebra, IMO, Olympiad, Problem Solving Tags: , ,
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: