2004 IMO Shortlist Problems/A2
Problem
(Mihai Bălună, Romania)
An infinite sequence of real numbers satisfies the condition
for every
,
with and
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 is called a bs sequence if
, for all
. Prove that a bs sequence is bounded if and only if the function
given by
, for all
is the null function.
Contents
[hide]Solution
Solution 1
We note that each of the 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 , then
, so
. Furthermore, since
,
.
Consider a sequence of positive reals which obeys the recursive relation

Lemma 2. .
Proof. We note that if , then
and
. Thus if
, we must have
, a contradiction.
Lemma 3. Let ,
. Then
.
Proof. For , easy induction yields
,
,
.
Now, if is even, we have
, which is less than
by the definition of
, and
,
,
. Since
and
add to
, one of them must be at most
, and the lemma follows.
On the other hand, if is odd, then set
and we have
,
, and
, so as before, at least one of
,
must be at most
. In fact, we have
, so the minimum of
is at most
, upholding the lemma, since in this case
.
Now, suppose that is bounded, i.e., there exists some real
greater than each
. By setting
equal to
, we generate the first
of the
in reverse, and from Lemma 2, we can see that
is a lower bound of the
. But by making
greater than
, by applying Lemma 3, we obtain the result
, which is a contradiction when
are distinct and greater than 0, by Lemma 1.
Now, if for all natural
, all the nonzero
must be equal and the sequence is bounded. On the other hand, if
always holds, then either
and
, or one of
is equal to zero and
is equal to the other one; hence by induction, all the nonzero terms of the sequence are equal, and
is always equal to zero. Hence if for some
,
, 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 if
, and
otherwise. Note that if
, then
.
Lemma 1: Let be the minimal element of
. Then
.
Proof: Suppose is the minimal value of
such that
. Then
, so
, and
. This contradicts our assumption of minimality.
Let ; we claim that
, which would imply that
is unbounded, in turn implying that
is unbounded.
- Suppose
; then
or
. In the former case,
so
, and
. In the latter case,
.
- Suppose
,
; then
, and
. Then
.
Then , so
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 of real numbers satisfying
for
:
i) the sequence is bounded;
ii) the function defined by
, for
, is identically zero;
iii) the sequence is of the form with
.