排序不等式

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

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

得證。