Problem: Show that the inequality
\[\sum_{i=1}^n \sum_{j=1}^n \sqrt{|x_i-x_j|}
  \le \sum_{i=1}^n \sum_{j=1}^n \sqrt{|x_i+x_j|} \]
holds for all real numbers $x_1$, $x_2$, \dots, $x_n$.

Solution: The proof is by induction on $n \ge 1$ with the base cases $n=1$ and
$n=2$ being easy to verify by hand.

In the general situation, consider replacing the tuple $(x_i)_i$
with $(x_i+t)_i$ for some parameter $t \in \RR$.
The inequality becomes
\[\sum_{i=1}^n \sum_{j=1}^n \sqrt{|x_i-x_j|}
  \le \sum_{i=1}^n \sum_{j=1}^n \sqrt{|x_i+x_j+2t|}. \]
The left-hand side is independent of $t$.
\begin{claim*}
  The right-hand side, viewed as a function $F(t)$ of $t$,
  is minimized when $2t = -(x_i + x_j)$ for some $i$ and $j$.
\end{claim*}
\begin{proof}
  Since $F(t)$ is the sum of piecewise concave functions,
  it is hence itself piecewise concave.
  Moreover $F$ increases without bound if $|t| \to \infty$.

  On each of the finitely many intervals on which $F(t)$ is
  concave, the function is minimized at its endpoints.
  Hence the minimum value must occur at one of the endpoints.
\end{proof}

If $t = -x_i$ for some $i$, this is the same as shifting all the
variables so that $x_i = 0$.
In that case, we may apply induction on $n-1$ variables,
deleting the variable $x_i$.

If $t = -\frac{x_i+x_j}{2}$, then notice
\[ x_i + t = -(x_j + t) \]
so it's the same as shifting all the variables such that $x_i = -x_j$.
In that case, we may apply induction on $n-2$ variables,
after deleting $x_i$ and $x_j$.