Stuck trying to prove an inequality I have been trying to prove (the left half of) the following inequality:
$$ \underbrace{\sum_i \sum_j |x_i| \le \sum_i \sum_j |x_i + x_j|}_\textrm{?} \le 2 \sum_i \sum_j |x_i|$$
(All $x_i$s are arbitrary reals and sums are over $1, 2, \dots, n$)
The right half follows by a simple application of the triangle inequality, but the left half isn't as simple.
I tried induction, and I could reduce the above problem to proving the following statement:
$$ \sum_i |x_i + x_{n+1}| + \sum_{i=1}^{n+1} |x_i + x_{n+1}| \ge \sum_{i=1}^{n+1} |x_i| + n|x_{n+1}|$$
or more simply (replacing $x_{n+1}$ by $y$),
$$ 2\sum_i |x_i + y| \ge \sum_i |x_i| + (n-1)|y|$$
However, I don't know if the above "reduction" is any simpler than the original problem itself!
Can I continue the above line of thought, or is there an easier way to solve this problem? Any help is appreciated! :)
 A: I believe that some clever tricks will solve the problem (e.g. by recasting the inequality into the form of some known inequality), but what came to mind first was a proof inspired by the simplex method. Although it isn't clever, it may be of some interests to the readers:

*

*By scaling the inequality, we may assume without loss of generality that $|x_i|\le1$ for all $i$.

*So we want to prove the inequality for all $(x_1,\ldots,x_n)$ inside the hypercube $[-1,1]^n$.

*Divide the hypercube $[-1,1]^n$ into pieces by the hyperplanes $x_i=x_j$ and $x_i=0$. For instance, when $n=2$, the four "hyperplanes" (straight lines in this case) $x=y$, $x=-y$, $x=0$ and $y=0$ divide the square region $[-1,1]^2$ into eight pieces in a manner akin to the Union Jack.

*In mathematics, we call each of these pieces a simplex.

*Inside each simplex, each $x_i$ or $x_i+x_j$ does not change sign.

*Therefore, inside each simplex, the function $f(x_1,\ldots,x_n)=-\sum_i \sum_j |x_i| + \sum_i \sum_j |x_i + x_j|$ is identical to $-\sum_i \sum_j s_ix_i + \sum_i \sum_j t_{ij}(x_i + x_j)$ for some constants $s_i, t_{ij}=\pm1$.

*In other words, $f$ is a linear function inside each simplex.

*In linear programming, it is well known that the extremum of a linear function can be attained at the corners of the simplex. You can imagine that when you move a plane closer and closer to a simplex, it will touch the simplex at a corner first (or it touches the whole face, with the corners of the face included).

*The corners of our simplices, however, are those points at which $x_i\in\{-1,0,1\}$.

*So, we only need to prove the inequality at these corner points.

*Let $a$ of the $x_i$s are equal to 1, $b$ of them are equal to $-1$ and $n-a-b$ of them are equal to zero. Then
$$
\begin{align}
&-\sum_i \sum_j |x_i| + \sum_i \sum_j |x_i + x_j|\\
=&-n(a+b) + \left[2a^2+2b^2+2a(n-a-b)+2b(n-a-b)\right]\\
=&2a^2+2b^2 - 2(a+b)^2 + n(a+b)\\
\ge&2a^2+2b^2 - 2(a+b)^2 + (a+b)^2\\
=&(a-b)^2\\
\ge&0.
\end{align}
$$

*Hence the result.

In step 11 above, equality holds iff $a-b=0$ and $a+b\in\{0,n\}$. In other words, equality holds iff $a=b=0$ or $a=b=n/2$, that is, iff all $x_i$s are zero, or when $n$ is even, exactly half of the $x_i$s (before scaling) are identical to some $x$ and the other half are $-x$s. However, this condition for equality is derived under the assumption that $(x_1,\ldots,x_n)$ is a corner point. It does not tell us when or whethere equality holds at other points in the simplices.
A: Assume an ordering of the $x_i$ such that $x_1 \le x_2 \le \dots \le x_k < 0 \le x_{k+1} \le x_{k+2} \le \dots \le x_n$. Let's call $T_1 = \sum_{i=1}^k |x_i|$, $T_2 = \sum_{i=k+1}^n |x_i|$, and $T=\sum_i |x_i|=T_1+T_2$ so that $T, T_1, T_2 \ge 0$.
Since we only require a lower bound on the sum $\sum_{i \neq j} |x_i + x_j|$, we only consider $2\binom{k}{2} + 2\binom{n-k}{2}$ terms of the $2\binom{n}{2}$ total terms that the sum contains i.e. we only pick terms where both $x_i$ and $x_j$ have the same sign. This solves the inequality in many cases. For the other cases, we include the cross terms too later.
$$
\begin{align*}
\sum_{i \neq j} |x_i + x_j| &\ge \sum_{i=1}^k \sum_{j=1,j\neq i}^k |x_i+x_j| + \sum_{i=k+1}^n \sum_{j=k+1,j\neq i}^n |x_i+x_j|\\
&= \sum_{i=1}^k \sum_{j=1,j\neq i}^k (|x_i|+|x_j|) + \sum_{i=k+1}^n \sum_{j=k+1,j\neq i}^n (|x_i|+|x_j|)\\
&= \sum_{i=1}^k ((k-1)|x_i|+T_1-|x_i|) + \sum_{i=k+1}^n ((n-k-1)|x_i|+T_2-|x_i|)\\
&= \sum_{i=1}^k ((k-2)|x_i|+T_1) + \sum_{i=k+1}^n ((n-k-2)|x_i|+T_2)\\
&= ((k-2)T_1+kT_1) + ((n-k-2)T_2+(n-k)T_2)\\
&= 2\{(k-1)T_1 + (n-k-1)T_2\}\\
\end{align*}
$$
Now, the last expression is a function of $T_1$ and $T_2$. Since we require a lower bound in terms of $T=T_1+T_2$, we can get two equivalent expressions in terms of either $T_1$ and $T$ or in terms of $T_2$ and $T$. Thus,
$$\sum_{i \neq j} |x_i + x_j| \ge 2(2k-n)T_1+2(n-k-1)T$$
$$\sum_{i \neq j} |x_i + x_j| \ge 2(n-2k)T_2+2(k-1)T$$
Adding both, we get:
$$2\sum_{i \neq j} |x_i + x_j| \ge 2\left\{(2k-n)T_1+(n-2k)T_2+(n-2)T\right\}$$
$$\implies \sum_{i \neq j} |x_i + x_j| \ge (2k-n)(T_1-T_2)+(n-2)T \ge (n-2)\sum_i |x_i|$$
$$ \text{whenever,} \; (2k-n)(T_1-T_2) \ge 0$$
For the cases when the above inequality doesn't hold, we need to consider the cross terms too. Computing the cross terms alone:
$$
\begin{align*}
\sum_{i \neq j} |x_i + x_j| &\ge \sum_{i=1}^k \sum_{j=k+1}^n |x_i+x_j| + \sum_{i=k+1}^n \sum_{j=1}^k |x_i+x_j|\\
&\ge 2\sum_{i=1}^k \sum_{j=k+1}^n |x_i+x_j|\\
&\ge 2\sum_{i=1}^k \sum_{j=k+1}^n \max\{|x_i|-|x_j|,|x_j|-|x_i|\}\\
&\ge 2 \max\{(n-k)T_1-kT_2, kT_2-(n-k)T_1\}\\
\end{align*}
$$
Including the cross terms along with the terms from the previous case, we have:
$$
\begin{align*}
\sum_{i \neq j} |x_i + x_j| &\ge 2 \max\{(n-k)T_1-kT_2, kT_2-(n-k)T_1\} + 2\{(k-1)T_1 + (n-k-1)T_2\}\\
 &\ge 2 \max\{(n-1)T_1+(n-2k-1)T_2, (2k-n-1)T_1+(n-1)T_2\} \; (*)\\
\end{align*}
$$
The $\max$ term can go one of two ways. Using the first term we get:
$$
\sum_{i \neq j} |x_i + x_j| \ge 2 \{(n-1)T_1+(n-2k-1)T_2\}
$$
We can again write the above in terms of either $T,T_1$ or $T,T_2$ giving two inequalities:
$$
\begin{align}
\sum_{i \neq j} |x_i+x_j| &\ge (n-2k-1)T+2kT_1\\
\sum_{i \neq j} |x_i+x_j| &\ge (n-1)T-2kT_2
\end{align}
$$
Summing the above two inequalities,
$$
\begin{align*}
\sum_{i \neq j} |x_i + x_j| &\ge (2n-2k-2)T+2k(T_1-T_2)\\
&\ge (n-2)T+(n-2k)T+2k(T_1-T_2)\\
&\ge (n-2)T \quad \text{for the case} \quad (2k-n) \le 0, (T_1-T_2) \ge 0\\
\end{align*}
$$
Similarly, for the other case, when $(2k-n) \ge 0, (T_1-T_2) \le 0$, we use the other $\max$ term from $(*)$ and follow the above steps routinely to prove the inequality.
Q.E.D
A: Let $p$ be the number of $x_i\ge0$, $m$ be the number of $x_i<0$, and $n=p+m$.
$$
\small\begin{array}{}
&\sum_i\;\:\sum_j|x_i+x_j|\\
&=\sum_{x_i\ge0}\;\:\sum_{x_j\ge0}|x_i+x_j|
&+\sum_{x_i\ge0}\;\:\sum_{x_j<0}|x_i+x_j|
&+\sum_{x_i<0}\;\:\sum_{x_j\ge0}|x_i+x_j|
&+\sum_{x_i<0}\;\:\sum_{x_j<0}|x_i+x_j|\\
&\ge\sum_{x_i\ge0}\;\:\sum_{x_j\ge0}|x_i|+|x_j|
&+\left|\sum_{x_i\ge0}\;\:\sum_{x_j<0}|x_i|-|x_j|\right|
&+\left|\sum_{x_i<0}\;\:\sum_{x_j\ge0}|x_j|-|x_i|\right|
&+\sum_{x_i<0}\;\:\sum_{x_j<0}|x_i|+|x_j|\\
&=2p\sum_{x_i\ge0}|x_i|
&+2\left|m\sum_{x_i\ge0}|x_i|-p\sum_{x_i<0}|x_i|\right|
&&+2m\sum_{x_i<0}|x_i|
\end{array}
$$
Subtracting $\displaystyle\sum_i\;\:\sum_j|x_i|=n\sum_i\;|x_i|$ from the inequality above yields
$$
\small\begin{align}{}
&\sum_i\;\:\sum_j|x_i+x_j|-\sum_i\;\:\sum_j|x_i|\\
&\ge(p-m)\sum_{x_i\ge0}|x_i|
+\left|2m\sum_{x_i\ge0}|x_i|-2p\sum_{x_i<0}|x_i|\right|
+(m-p)\sum_{x_i<0}|x_i|\\
&=(p-m)\sum_{i}x_i
+\left|(m-p)\sum_{i}|x_i|+n\sum_ix_i\right|\\
&\ge0\tag{1}
\end{align}
$$
In the last inequality, if $p-m$ and $\sum\limits_ix_i$  have the same sign, we can ignore the quantity in absolute values.  If $p-m$ and $\sum\limits_ix_i$ have different signs, then the quantities in the absolute values have the same sign and $|m-p|\sum\limits_i|x_i|\ge(m-p)\sum\limits_ix_i$.
Therefore, $(1)$ says that
$$
\sum_i\;\:\sum_j|x_i|\le\sum_i\;\:\sum_j|x_i+x_j|
$$
