# 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.*