排序不等式

排序不等式是数学上的一条不等式。它可以推导出很多有名的不等式，例如算术几何平均不等式（简称算几不等式），柯西不等式，和切比雪夫总和不等式。它是说：

如果 $x_{1}\leq x_{2}\leq \cdots \leq x_{n}$，和 $y_{1}\leq y_{2}\leq \cdots \leq y_{n}$ 是两组实数。而 $x_{\sigma (1)},\ldots ,x_{\sigma (n)}$ 是$x_{1},\ldots ,x_{n}$的一个排列。排序不等式指出 $x_{1}y_{1}+\cdots +x_{n}y_{n}\geq x_{\sigma (1)}y_{1}+\cdots +x_{\sigma (n)}y_{n}\geq x_{n}y_{1}+\cdots +x_{1}y_{n}$。

以文字可以说成是顺序和不小于乱序和，乱序和不小于逆序和。与很多不等式不同，排序不等式不需限定$x_{i},\,y_{i}$的正负。

证明

排序不等式可以用数学归纳法证明。关键在于下列结果：

若 $x_{i}\leq x_{j},\,y_{i}\leq y_{j}$，则有 $(x_{j}-x_{i})(y_{j}-y_{i})\geq 0$

移项得出 $x_{i}y_{i}+x_{j}y_{j}\geq x_{j}y_{i}+x_{i}y_{j}$。

重复以上步骤便可得出排序不等式。

我们设 $S_{i}$ 为 $b_{1},b_{2},\dots b_{n}$ 原序列的前 $i$ 个数的和，即 $S_{i}=b_{1}+b_{2}+\dots b_{i}$。

设 $S'$ 为打乱顺序后的序列，$S'_{i}$ 表示乱序后的前 $i$ 个数的和。所以有 $S_{i}\leq S'_{i}$。

注意到 $a_{n}-a_{n+1}\leq 0$，则 $S_{i}\times (a_{n}-a_{n+1})\geq S'_{i}\times (a_{n}-a_{n+1})$

$\sum _{k=1}^{n}a_{k}b_{k}=\sum _{k=1}^{n-1}S_{k}(a_{k}-a_{k+1})+S_{n}a_{n}\geq \sum _{k=1}^{n-1}S'_{k}(a_{k}-a_{k+1})+S'_{n}a_{n}(S'_{n}=S_{n})$

得证。