排序不等式证明

· · 个人记录

注：

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

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

排序不等式简介

排序不等式是数学上的一条不等式。它是说：如果 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 。

证明完毕。