排序不等式

排序不等式是數學上的一條不等式。它可以推導出很多有名的不等式，例如算術幾何平均不等式（簡稱算幾不等式），柯西不等式，和切比雪夫總和不等式。它是說：

如果 ${\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}*(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})}$ 

得证。