Let A be a non-empty finite sequence of n distinct integers $a_1 \lt a_2 \lt...\lt a_n$. Define $B=\{a_i +a_j | 1\le i,j \le n\}$ For example if $A=\{1,4\} , B =\{2,5,8\}$.How do you show that $$|B| \ge 2n-1$$ where |B| means the number of elements in B?
How should I approach these kind of sums? I think that somehow the least value of |B| will be when A contains an arithmetic progression but how should I prove it? Please help.
The basic idea here is to find $2n-1$ explicit elements of $B$ that you know are different. How can you be sure they're different? One way is to choose them in such a way that you know each one is smaller than the last.
Imagine your original set consists of $a_1<a_2<...<a_n$. Once you sort it that way, it's clear what the smallest number of the sumset is: $a_1+a_1$. How do I make it slightly bigger? Replace $a_1$ by $a_2$ to get $a_1+a_2$. And I can make that even bigger by instead doing $a_1+a_3$. Then $a_1+a_4$, and so on until I reach $a_1+a_n$. Now I can't increase the second number anymore. But I can increase the first: $a_1+a_n<a_2+a_n$. And that's smaller than $a_3+a_n$... Continuing in this fashion, you'll eventually reach $2n-1$ different numbers.
I like visualizing this argument as taking place on the $n \times n$ grid with rows indexed by the first thing you're adding, and columns by the second. Each time you step to the right or up, you make the sum bigger. And moving from $(1,1)$ to $(n,n)$ by the path of your choice you use $2n-1$ points.