1999 BMO Problems/Problem 4

Problem

Let $\{a_n \}_{n\ge 0}$ be a non-decreasing, unbounded sequence of non-negative integers with $a_0=0$ . Let the number of members of the sequence not exceeding $n$ be $b_n$ . Prove that for all positive integers $m$ and $n$ , we have $a_0 + a_1 + \dotsb + a_m + b_0 + b_1 + \dotsb + b_n \ge (m+1)(n+1) .$

Solution

Note that for arbitrary nonnegative integers $i,j$ , the relation $j \le a_i$ is equivalent to the relation $i \ge b_{j-1}$ . It then follows that $\sum_{i=0}^m a_i = \sum_{i=0}^m \sum_{j=1}^{a_i} 1 = \sum_{j=1}^{a_m} \sum_{i=b_{j-1}}^m 1 = \sum_{j=1}^{a_m} ( m+1 - b_{j-1} ) = \sum_{j=0}^{a_m-1} (m+1 - b_j ) .$ Note that if $j \le a_m-1$ , then there are at most $m$ terms of $\{ a_k\}_{k\ge 0}$ which do not exceed $j$ , i.e., $b_j \le m$ ; it follows that every term of the last summation is positive.

Now, if $a_m \ge n+1$ , then we have $\begin{align*} \sum_{i=0}^m a_i + \sum_{j=0}^n b_j &= \sum_{j=n+1}^{a_m-1}(m+1 - b_j) + \sum_{j=0}^n (m+1 - b_j + b_j) \\ &= \sum_{j=n+1}^{a_m-1}(m+1-b_j) + (n+1)(m+1) \ge (n+1)(m+1), \end{align*}$ as desired. On the other hand, if $a_m < n+1$ , then for all $j\ge a_m$ , $b_j \ge m+1$ . It then follows that $\begin{align*} \sum_{i=0}^m a_j + \sum_{j=0}^n b_j &= \sum_{j=0}^{a_m-1}(m+1 - b_j + b_j) + \sum_{j=a_m}^n b_j \\ &= (a_m)(m+1) + \sum_{j=a_m}^n b_j \\ &\ge (a_m)(m+1) + (n+1-a_m)(m+1) = (n+1)(m+1), \end{align*}$ as desired. Therefore the problem statement is true in all cases. $\blacksquare$