注：

本文多有疏漏，敬请谅解。如有建议请在评论区留言，我会及时更正。谢谢。

本文希望提供较为严谨的排序不等式证明。有的地方作者能力不足或者说不清楚的，也许会不当地使用“显然”之类模糊不清的词，还请读者海涵。

排序不等式简介

排序不等式是数学上的一条不等式。它是说：如果 $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$ 表示序列 $X$ 的第 $i$ 个元素，用 $y_i$ 表示序列 $Y$ 的第 $i$ 个元素。我们假设 $|X| = |Y| = n$ 。保证 $X$ 和 $Y$ 满足如下条件：
$$\forall_i (1<i \le n)\rightarrow(x_i \geq x_{i-1} \land y_i \geq y_{i-1})$$

顺序和 $\Alpha$ 定义如下：
$$A=\sum\limits_{i=1}^{n}x_i \times y_i$$
乱序和 $\Beta$ 定义如下：

我们定义序列 $C$ 表示 $Y$ 的一组全排列，即 $C$ 中的每一个元素都在 $Y$ 当中，且 $Y$ 中的每一个元素都在 $C$ 当中，且 $|Y|=|C|$ 。

我们用 $c_i$ 表示 $C$ 的第 $i$ 个元素。
$$B=\sum\limits_{i=1}^n x_i \times c_i$$
逆序和 $\Gamma$ 定义如下：
$$\Gamma = \sum \limits _{i=1} ^n x_i \times y_{n-i+1}$$
我们首先证明 $n=1$ 时 $\Alpha \geq \Beta \geq \Gamma$ ：

显然的是，$Y$ 的全排列有且仅有一种，即 $(y_1)$ ，那么乱序和只能是 $x_1 \times y_1$ 。我们也会发现，顺序和和逆序和同样都是 $x_1 \times y_1$ 。于是 $\Alpha \geq \Beta \geq \Gamma$ 成立。

接下来我们证明假设 $n=k(k\geq 1)$ 时 $\Alpha \geq \Beta \geq \Gamma$ ，那么 $n=k+1$ 时 $\Alpha \geq \Beta \geq \Gamma$ 。

当 $c_{k+1} = y_{k+1}$ 时，假设存在一个排列 $C$ 使得 $\Beta>\Alpha$ ，那么我们可以推导出如下式子：
$$\sum\limits_{i=1}^k x_i \times c_i > \sum\limits_{i=1}^{k}x_i \times y_i$$
与假设矛盾，故 $\Alpha \geq \Beta$。

同理，当 $c_{k+1} = y_1$ 时，假设存在一个排列 $C$ 使得 $\Beta < \Gamma$，那么我们可以推导出如下的式子：
$$\sum\limits_{i=1}^k x_i \times c_i < \sum \limits _{i=1} ^k x_i \times y_{(k+1)-i+1}$$
与假设矛盾，故 $\Beta \geq \Gamma$ 。

当 $c_{k+1} \ne y_{k+1}$ 时，我们假设 $c_i = y_{k+1}$ 。

我们先证明如下式子成立：
$$a_i \times c_i + a_{k+1} \times c_{k+1} \leq a_i \times c_{k+1} + a_{k+1} \times c_i$$

证明如下：
$$(a_{k+1} - a_{i})\times(c_i -c_{k+1})\geq 0$$
这个式子很容易得出来，因为 $a_{k+1} \geq a_i$ ， $c_i = y_{k+1} \geq c_{k+1}$ 。

展开后如下:
$$a_{k+1} \times c_i - a_{k+1} \times c_{k+1} -a_i \times c_i + a_i \times c_{k+1} \geq 0$$
移项之后得到：
$$a_i \times c_i + a_{k+1} \times c_{k+1} \leq a_i \times c_{k+1} + a_{k+1} \times c_i$$
证明完毕。

于是我们可以得到，不论 $C$ 怎样排列，只要 $c_{k+1} \ne y_{k+1}$ ，都必然存在一种大于等于它的方案，也即 $c_{k+1} = y_{k+1}$ 时的方案。

而当 $c_{k+1} = y_{k+1}$ 时，最大的乘积之和就是 $\Alpha$ 。

于是，我们证明了 $\Alpha \geq \Beta$。

接下来我们证明当 $c_{k+1} \ne y_1$ 时，也有 $\Beta \geq \Gamma$ 。

我们首先假设 $c_i = y_1$ 。

我们先证明如下式子成立：
$$a_i \times c_i + a_{k+1} \times c_{k+1} \geq a_i \times c_{k+1} + a_{k+1} \times c_i$$
证明如下：
$$(a_{k+1} - a_i)\times(c_{k+1} - c_i) \geq 0$$
这个式子很好证明，因为 $a_{k+1}\geq a_i$ ，$c_i = y_1 \leq c_{k+1}$ 。

展开后如下：
$$a_{k+1} \times c_{k+1} +a_i \times c_i - a_i \times c_{k+1} -a_{k+1} \times c_i \geq 0$$
移项后可以得到：
$$a_i \times c_i + a_{k+1} \times c_{k+1} \geq a_i \times c_{k+1} + a_{k+1} \times c_i$$
证明完毕。

于是我们可以得到，不论 $C$ 怎样排列，只要 $c_{k+1}\ne y_1$，都必然存在一种小于等于它的方案，也即 $c_{k+1} = y_{1}$ 时的方案。

而当 $c_{k+1} = y_1$ 时，最小的乘积之和就是 $\Gamma$ 。

于是，我们证明了 $\Beta \ge \Gamma$ 。

到此，我们证明了对于所有的 $n \in N^+$ 都有 $\Alpha \geq \Beta \geq \Gamma$ 。

证明完毕。