2006 IMO Shortlist Problems/A1
Problem
(Estonia)
A sequence of real numbers is defined by the formula
for
;
here is an arbitrary real number,
denotes the greatest integer not exceeding
, and
. Prove that
for
sufficiently large.
Solution
We first note that for all nonnegative integers ,
,
so is a non-increasing function of
. We also note that if
is not positive (resp. not negative), then
is not positive (resp. not negative).
When ,
. It follows that if
is nonnegative, it is enough to show that for
, then
, for then we must eventually have
. But this comes from
.
We prove the result for negative by induction on
. For our base case,
, we either have
and
for positive
. For
, we have
.
Now, suppose that the statement holds for . If ever we have
, then the problem reduces to a previous case. Therefore if we ever have
, then the problem reduces to a previous case. Therefore if
generates a counterexample to the problem, then we must always have
.
Then if is a counterexample with
, then for nonnegative
, we must have
.
It follows by induction that
.
In particular, for all even integers , we have
.
Since becomes arbitrarily close to
as
becomes arbitrarily large, we thus have
.
But for odd integers , the inequality is reversed, and we have
,
and similarly,
.
It follows that is of the form
, for some positive integer
. But this gives us a constant sequence, which is not a counterexample. Therefore by induction, there are no negative counterexamples. Since we have already proven that the problem statement holds for nonnegative reals, we are done. ∎
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.