The proof goes like 1. estimate a upper bound of and 2. find and that satisfies the constraint and achieves the upper bound.

Let's say (binary) and , then we can construct:

(put 1 at the most significant bit followed by 0s) and

(put 0 at the most significant bit followed by 1s)

so that . And the constraints are also satisfied.

Hope this example helps.