2006 IMO Shortlist Problems/A1
(Estonia) A sequence of real numbers is defined by the formula
here is an arbitrary real number, denotes the greatest integer not exceeding , and . Prove that for sufficiently large.
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
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.