Difference between revisions of "1999 BMO Problems/Problem 4"
(New page: == Problem == Let <math>\{a_n \}_{n\ge 0}</math> be a non-decreasing, unbounded sequence of non-negative integers with <math>a_0=0</math>. Let the number of members of the sequence not e...) |
(No difference)
|
Latest revision as of 14:59, 28 December 2007
Problem
Let be a non-decreasing, unbounded sequence of non-negative integers with . Let the number of members of the sequence not exceeding be . Prove that for all positive integers and , we have
Solution
Note that for arbitrary nonnegative integers , the relation is equivalent to the relation . It then follows that Note that if , then there are at most terms of which do not exceed , i.e., ; it follows that every term of the last summation is positive.
Now, if , then we have as desired. On the other hand, if , then for all , . It then follows that as desired. Therefore the problem statement is true in all cases.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.