Help with simplifying summation Let $x \in \mathbb{R}^n$ be a vector of non-negative numbers $x = (x_1, \ldots, x_n)$ with mean $\bar{x}$.
I would like to prove that
$$\frac{\sum_{i = 1}^n \sum_{j = 1}^n \left| x_i - x_j \right|}{2 n^2 \bar{x}} = \frac{2 \sum_{i = 1}^n i(\tilde{x}_i - \bar{x})}{n^2 \bar{x}},$$
where $\tilde{x}$ contains the same elements as $x$ but sorted in ascending order. The rhs is computationally cheaper because I don't have to compute every possible absolute difference $\left|x_i - x_j\right|$.
Can I proceed using induction or maybe a manipulation of the lhs would yield directly the rhs, what do you think? Either ways seems tedious, I would appreciate any hints.
 A: \begin{align} \sum_{i=1}^n\sum_{j=1}^n|x_i-x_j|&=2\sum_{i=1}^{n}\sum_{j=i+1}^n(\tilde x_j-\tilde x_i)=2\sum_{i=1}^n-\tilde x_i(n-i)+2\sum_{i=1}^n\sum_{j=i+1}^n\tilde x_j\\&=2\sum_{i=1}^n-\tilde x_i(n-i)+2\sum_{i=1}^n (i-1)\tilde x_i\\
&=2\sum_{i=1}^n(2i-n-1)\tilde x_i\\
&=2\sum_{i=1}^n2i\tilde x_i-2(\frac2n\sum_{i=1}^n\tilde x_i)\frac{n(n+1)}2\\
&=2\sum_{i=1}^n2i\tilde x_i-4\left(\frac1n\sum_{i=1}^n\tilde x_i\right)\times\sum_{i=1}^ni
\end{align}
$$\boxed{\sum_{i=1}^n\sum_{j=1}^n|x_i-x_j|=4\sum_{1=1}^ni(\tilde x_i-\bar{x})}$$
Explanation
Line 1: Due to symmetry, it is unnecessary to sum all terms from $j=1$ to $n$. The term $\widetilde x_i$ is independent of $j$ so it can be taken out of the first sum to get $$\widetilde x_i \sum_{j=i+1}^n 1$$
Line 2: Similarly to Fubini's Theorem in calculus the two sums of the $\tilde x_j$ term in the first line can be switched while appropriately changing the boundaries. More intuitively this corresponds to adding the following terms from top to bottom (by column) instead of left to right (by row):
\begin{matrix}
x_2&x_3&x_4&x_5&\cdots&x_n\\
&x_3&x_4&x_5&\cdots&x_n\\
&&x_4&x_5&\cdots&x_n\\
&&&\vdots
\end{matrix}
P.S.: The form obtained in the third line, although having the same order of complexity as the final form, is probably faster for smaller values of $n$.
