ISI2018-PCB-A4

Question

Let $A$ and $B$ are two non-empty finite subsets of $\mathbb{Z}$, the set of all integers. Define  $A+B=\{a+b:a\in A,b\in B\}$.Prove that $\mid A+B \mid \geq \mid A \mid + \mid B \mid -1 $, where $\mid S \mid$ denotes the cardinality of finite set $S$.

Answer 1

We can order the elements of the sets A and B in ascending order that is :
$A$={$a_1,a_2,a_3,...,a_|A_| $} , $B$={$b_1,b_2,b_3,...,b_|B_|$}
Now , firstly we add $a_1$ with all elements of $B$, so we get $|B|$ elements.

Now if we try to do so, there can be several repetitions of the same value, hence we cannot correctly estimate the bound of set $A+B$.

$\therefore$ what we do is add the remaining elements of $A$ i.e $a_2,a_3....,a_n$ with $b_|B_|$ , this will surely generate a new value every time , as it will be greater than all the elements currently present in the set.
Total no. of elements in $A+B$ = |B| + |A|-1 $ [$\because$  we are adding from $a_2$ to $a_n$ , i.e $|A|-1$  elements]

$\therefore$ $|A+B|$  $\geq$ $|A|+|B|-1$

If something is not clear, please comment.