Cardinality of Set of Sums vs Set of Differences Let $A$ be a set of real numbers. Prove that the set of the real numbers that could be expressed as the sum of two not necessarily distinct elements of $A$ is at least as many elements as the set of nonnegative real numbers that could be expressed as the difference of two not necessarily distinct elements of $A$. 
I tried inducting on the size of $A$, and considering the intersections (where you don't get anything original because there's an overlap), but they do not seem to work.  Also I was able to note that you could refine it to "positive real numbers" because you could just shift the numbers up.
 A: Let $S$ be the set of sums $D$ the set of differences. Assume first that $A=\{x_1,\ldots,x_n\}$ is finite. The main issue is there is no canonical representation of elements from these sets, so to rectify this we construct a function $f$ on $P:=\{1,\ldots,n\}^2$ in the following way:


*

*We define $f$ in the order: $(1,1),(1,2),\ldots,(1,n),(2,1),\ldots,(2,n),\ldots,(n,1),\ldots,(n,n)$.

*$f(j,k)=1$ if $x_j+x_k\neq x_\ell+x_m$ for all previous pairs $(\ell,m)$. Otherwise, $f(j,k)=0$.


Let $F_0=\{(j,k)\in P\,:\,f(j,k)=0\}$, so $|S|=|P\setminus F_0|=|P|-|F_0|$. Notice that for every $(j,k)\in F_0$, there exists a unique minimal (with respect to the order above) pair $(\ell,m)\in F_1$ such that $x_j+x_k=x_\ell+x_m$, so in particular $x_j-x_m=x_\ell-x_k$. Let $R$ be the set of such pairs $(j,m)$ with $j,k,\ell,m$ as above. For every pair $(j,m)\in R$ there exists a pair $(\ell,k)\in P\setminus R$ such that $x_j-x_m=x_k-x_\ell$ (using a similar order argument). That is, for $(\ell,k)\in R$, $x_\ell-x_k$ has already been counted in $|D|$ by another pair; there may be more overcounting still in $P\setminus R$. Hence we have shown that
$$
|D|\le|P|-|R|=|P|-|F_0|=|S|.
$$
The infinite case is actually simpler: there are obvious injections $A\hookrightarrow S\hookrightarrow A\times A$ and $D\hookrightarrow A\times A$, but since $A$ is infinite there is also an injection $A\times A\hookrightarrow A$. Putting these together we find $D\hookrightarrow A\times A\hookrightarrow A\hookrightarrow S$.
A: Here is a sketch of a proof by induction for the finite case; I suspect a fully detailed (and probably more elegant) proof may be found in a book of solutions to olympiad type problems.
The statement holds for $|A|=1$, as both the set of sums and the set of non-negative differences have 1 element.
Suppose that the statement holds for all $A$ of finite cardinality up to and including $n-1$, where $n \ge 2$.  Consider an arbitrary finite $A$ with $n$ elements, denoted as usual by $|A|=n$.
We want to prove that there are at least as many pairwise sums as non-negative pairwise differences, or (in notation to be introduced in the next paragraph) that $|S(A)|\ge |D(A)|$.
Let $a$ be the maximal element of the finite set $A$.
For convenience let $Aa$ denote the set $A\setminus\{a\}$ of all elements of $A$ excluding $a$, and let $S(X)=\left\{x+y\mid x,y\in X\right\}$ denote the set of sums of elements from $X$,
$Sf(X,x)= \left\{x+y\mid y\in X\right\}$ denote the set of sums where one element in each sum is fixed,
$D(X)=\left\{|x-y|\mid x,y\in X\right\}$ denote the set of differences,
and $Df(X,x)=\left\{|x-y|\mid y\in X\right\}$ denote the set of differences where one element in each difference is fixed.
Then $S(A) = S(Aa) \cup Sf(A,a)$ and $D(A) = D(Aa) \cup Df(A,a)$.
Note also that $|Df(A,a)| \le |Sf(A,a)| = n$, and that by the inductive hypothesis $|D(Aa)| \le |S(Aa)|$.
Although $a+a\in Sf(A,a)\setminus S(Aa)$, there may be some overlap of up to $n-1$ elements between $S(Aa)$ and $Sf(A,a)$.
We will show that whenever there is an overlapping value, then there is at least one corresponding overlapping value between $D(Aa)$ and $Df(A,a)$, in a precise sense.
Suppose $|S(A)|=|S(Aa)|+|Sf(A,a)|-k$.
We want to show that $|D(A)|\le|D(Aa)|+|Df(A,a)|-k$.
If $k=0$ then we are done.
Otherwise there is a subset $B\subseteq Aa$ with $k\ge 1$ elements, such that a value of the form $a+y$ for each $y\in B$ can be obtained as a sum of elements from $Aa$, so $a+y=u_y+v_y$ for some $u_y,v_y\in Aa$.
Now $|a-u_y| = a-u_y = v_y-y = |v_y-y|$, and therefore $|a-u_y|\in Df(A,a)\cap D(Aa)$.
Also, $|\{u_y+v_y\mid y\in B\}| = k$ so the set $\{|a-u_y| \mid y\in B\} \cup \{|a-v_y|\mid y\in B\}$ contains at least $k$ different elements.
It follows that $|D(A)| \le |D(Aa)|+|Df(A,a)|-k \le |S(A)|$.
The result therefore follows for any finite sets $A$.
Extending the argument to the infinite case requires a different approach, as a maximal element may not be available, and the construction of an injection from $D(A)$ to $S(A)$ needs more care.
