Show that $A+B$ contains at least $m+n-1$ elements.

Question

Let $A,B \subset \mathbb Z$ such that $|A|=m$ and $|B|=n$. Then show that $|A+B| \geq m+n-1$.

How can I proceed? I have tried to proceed by using law of trichotomy but I only managed to find $\mathrm {max} (m,n)$ elements in $|A+B|$. How should I proceed?

Thank you in advance.

Answer 1

Write $A=\{a_1,...,a_m\}$ where $a_1<a_2<...<a_m$.

And $B=\{b_1,...,b_n\}$ where $b_1<b_2<...<b_n$

then $a_m+b_m>a_m+b_{m-1}>a_{m-1}+b_{m-1}....>a_1+b_1$

and so these are $n+m-1$ different elements in $A+B$.

Answer 2

Say $A=\{a_1<a_2<...<a_m\}$ and $B =\{b_1<b_2<...<b_n\}$, then

$$a_1+b_1<a_1+b_2<a_1+b_3<...<a_1+b_n<a_2+b_n<...<a_m+b_n$$

so we have at least $m+n-1$ different sums and we are done.