有序实数序列下|xᵢ - xⱼ|双重求和推导求助
Hey Jonathan，我来帮你梳理这个双重求和的推导过程～首先我得先确认一下，你这里的序列应该是有序的吧？看你展开的时候拆分了正负项，应该是默认序列是按从小到大（或者从大到小）排序的？我先假设序列是单调递增的，也就是 (x_1 \leq x_2 \leq \dots \leq x_n)，这样绝对值的处理就清晰了。
先把你的推导尝试整理一下：
我的推导进行到一半卡住了：
给定左边（LHS）：
$$\sum_{i=1}^n \sum_{j=1}^n |x_i - x_j|$$
我展开成：
$$\sum_{i=1}^n \left( |x_i - x_1| + |x_i - x_2| + \dots + |x_i - x_n| \right)$$
接着根据绝对值的性质拆分（假设序列单调递增）：
$$\sum_{i=1}^n \left[ (x_i - x_1) + (x_i - x_2) + \dots + (x_i - x_{i-1}) + |x_i - x_i| + (x_{i+1} - x_i) + \dots + (x_n - x_i) \right]$$
然后整理到这一步就卡壳了：
$$\sum_{i=1}^n \left[ (2i - n - 1)x_i - (x_1 + x_2 + \dots + x_i) + (x_{i+1} + x_{i+2} + \dots + x_n) \right]$$
其实你已经走对路啦！咱们把这个求和拆成几个部分来处理，会更清晰：
第一步：修正内层求和的系数
首先看你得到的系数(2i -n -1)，这里其实是个小失误：对于每个固定的i，内层求和里，(x_i)出现的次数是：
- 前i项（j≤i）：每个都是(x_i - x_j)，所以(x_i)加了i次
- 后n-i项（j>i）：每个都是(x_j - x_i)，所以(x_i)减了n-i次
所以(x_i)的总系数是(i - (n - i) = 2i -n)，不是(2i -n -1)哦～
第二步：利用对称性简化整体求和
因为(|x_i - x_j| = |x_j - x_i|)，整个双重求和里，每个无序对((i,j))（i≠j）会被计算两次（i,j和j,i），而i=j时项为0，所以我们可以把原式转化为：
$$\sum_{i=1}^n \sum_{j=1}^n |x_i -x_j| = 2\sum_{1 \leq i < j \leq n} |x_i -x_j|$$
因为序列是单调递增的，(j>i)时(|x_i -x_j|=x_j -x_i)，代入得：
$$2\sum_{1 \leq i < j \leq n} (x_j -x_i)$$
第三步：拆分求和计算每个(x_k)的系数
把这个求和拆成两部分：
$$2\left( \sum_{1 \leq i < j \leq n} x_j - \sum_{1 \leq i < j \leq n} x_i \right)$$
现在计算每个(x_k)在两个求和中的出现次数：
- 对于(\sum_{1 \leq i < j \leq n} x_j)：每个(x_k)作为j时，i可以取1到k-1，所以一共出现(k-1)次，总和为(\sum_{k=1}^n (k-1)x_k)
- 对于(\sum_{1 \leq i < j \leq n} x_i)：每个(x_k)作为i时，j可以取k+1到n，所以一共出现(n -k)次，总和为(\sum_{k=1}^n (n -k)x_k)
把这两个结果代入，合并求和：
$$2\sum_{k=1}^n \left[ (k-1) - (n -k) \right]x_k = 2\sum_{k=1}^n (2k -n -1)x_k$$
第四步：和你卡住的步骤衔接
回到你卡住的式子，咱们把它转化一下：
$$\sum_{i=1}^n \left[ (2i -n)x_i + (x_{i+1}+\dots+x_n) - (x_1+\dots+x_i) \right]$$
令前缀和(S_i = x_1+x_2+\dots+x_i)，那么(x_{i+1}+\dots+x_n = S_n - S_i)，代入得：
$$\sum_{i=1}^n \left[ (2i -n)x_i + S_n - 2S_i \right]$$
展开后：
$$\sum_{i=1}^n (2i -n)x_i + nS_n - 2\sum_{i=1}^n S_i$$
如果你把这个式子和我们用对称性得到的结果对比，其实是等价的，展开验证一下就能发现两者一致～
这样整个推导就通顺啦，你之前的思路完全正确，只是差了一步利用对称性简化，或者拆分后计算每个项的出现次数这一步。
备注：内容来源于stack exchange，提问作者Jonathan Ramachandran
