1999 BMO Problems/Problem 4
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
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.