排序不等式

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

如果 ${\displaystyle x_{1}\leq x_{2}\leq \cdots \leq x_{n}}$，和 ${\displaystyle y_{1}\leq y_{2}\leq \cdots \leq y_{n}}$ 是两组实数。而 ${\displaystyle x_{\sigma (1)},\ldots ,x_{\sigma (n)}}$ 是${\displaystyle x_{1},\ldots ,x_{n}}$的一个排列。排序不等式指出 ${\displaystyle 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}}$。

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

证明

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

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

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

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

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

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

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

${\displaystyle \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})}$

得证。