4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – Joshua Tilley Apr 26 '18 at 23:21
  • $\begingroup$ Sorry, I mean $\left|Z\right|\geq kn-k+1$ $\endgroup$ – Joshua Tilley Apr 26 '18 at 23:23
  • $\begingroup$ 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$. $\endgroup$ – Mike Earnest Apr 26 '18 at 23:28
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You mean $Y_{n-1}$ has at least $2(n-1) - 1$ elements. It can, of course, have more. $\endgroup$ – fleablood Apr 26 '18 at 22:05
  • $\begingroup$ Yes indeed, at least. I corrected that in my post. Good catch! $\endgroup$ – Mike Apr 26 '18 at 22:06
  • 1
    $\begingroup$ 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$, $\endgroup$ – Paul Frost Apr 26 '18 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.