# Bounds on the size of a set.

Let $X\subseteq\mathbb{R}$ with $\left|X\right|=n$ and define $Y=\left\{ x+y\vert x,y\in X\right\}$. Prove that $$\left|Y\right|\geq2n-1$$

Let $x_1<x_2<\dots<x_n$ be the sorted list of the elements of $X$. Then $$x_1+x_1<x_1+x_2<x_1+x_3<\dots<x_1+x_n<x_2+x_n<x_3+x_n<\dots <x_n+x_n$$ are $2n-1$ distinct members of $Y$, so $|Y|\ge 2n-1$.
• How about if $Z=\left\{ \sum_{i=1}^{k}x_{i}\vert x_{1},...,x_{k}\in X\right\}$ show $\left|Z\right|\geq\left(k-1\right)n+1$ – Joshua Tilley Apr 26 '18 at 23:21
• Sorry, I mean $\left|Z\right|\geq kn-k+1$ – Joshua Tilley Apr 26 '18 at 23:23
• For any sets, let $A + B = \{a+b:a\in A,b\in B\}$. Use the method in my post to prove the Lemma $|A+B|\ge |A|+|B|-1$. Since $Z=X+X+\dots+X$, with $k$ summands, you can use the lemma plus induction on $k$. – Mike Earnest Apr 26 '18 at 23:28
Use induction on $n$. Write $X = \{x_1, \ldots, x_n\}$, where $i<j$ implies $x_i < x_j$. Then by induction $Y_{n-1} =\{x_i+x_j; i,j < n\}$ has at least $2(n-1) - 1$ elements. But the two numbers $x_n +x_{n-1}$ and $x_{n} + x_{n-2}$ are each larger than any elements in $Y_{n-1}$, and are both in $Y$.
• You mean $Y_{n-1}$ has at least $2(n-1) - 1$ elements. It can, of course, have more. – fleablood Apr 26 '18 at 22:05
• One should take $x_n + x_n$ instead of $x_n + x_{n-2}$. The latter could be the same as $x_{n-1} + x_{n-1}$. Take e.g. $x_i = i$, – Paul Frost Apr 26 '18 at 22:22