Prove $|A + B| ≥ |A| + |B| - 1$

Question

Let A and B be two non-empty sets of real numbers. Define A + B to be the set $$A+B = \{ a + b : a ∈ A, b ∈ B\}$$ For instance, if $A =\{1,3,4\}$ and $B = \{1,3\}$, then $A + B =\{2,4,5,6,7\}$. show that in any case, we have $$|A + B| ≥ |A| + |B| - 1$$

Answer 1

A nice way to think about this is via orderings. In particular, you can put a partial order on the cartesian product $A\times B$ by saying $(a,b) \geq (a',b')$ if $a \geq a'$ and $b\geq b'$. Clearly, if $(a,b) > (a',b')$ then $a+b > a'+b'$. However, this product can be visualized as a grid with dimensions of $|A|$ by $|B|$; we can easily find ascending chains of length $|A|+|B|-1$ - whose sums must all be distinct because they are increasing.

To be really explicit, this argument tells us that if we write $A=\{a_1,\ldots,a_{|A|}\}$ and $B=\{b_1,\ldots,b_{|B|}\}$ in increasing order, we have that $A+B$ contains an increasing sequence \begin{align*}a_1&+b_1\\ a_2&+b_1\\ a_3&+b_1\\ &\,\vdots\\ a_{|A|-1}&+b_1\\ a_{|A|}&+b_1\\ a_{|A|}&+b_2\\ a_{|A|}&+b_3\\ &\,\vdots\\ a_{|A|}&+b_{|B|-1}\\ a_{|A|}&+b_{|B|} \end{align*} As this list is increasing from top to bottom, the elements in it must be distinct. There are $|A|+|B|-1$ elements in this list.

It is not too hard to extend this argument to find out that $|A+B| = |A|+|B|-1$ exactly if $A$ and $B$ are both arithmetic progressions of the same step size.