Bounds on the size of a set.

Question

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$$

Answer 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$.

Answer 2

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$.