Prove $|A + B| ≥ |A| + |B| - 1$ 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$$
 A: 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.
