排序不等式的两种证明方法

2019-09-26 本文已影响0人赫尔特

排序不等式：

（Discrete mathematics and its applications第6版习题）

1 （图片取自百度百科）
证明

数学归纳法：

$\begin{aligned} &当n=1时显然成立\\ &假设当n=k(k\geq2,k\in N_+)成立，\\ &则n=k+1时，由定义有a_{k+1}b_{k+1}\geq a_ib_j(i,j\leq k+1)\\ &又因为之前的假设:a_1b_1+a_2b_2+...a_kb_k是最大的\\ &假如我们的\{b_{k+1}\}有一个排列\{c_{k+1}\}\\ &使得乱序（非正序）乘积a_1c_1+a_2c_2+...a_{k+1}c_{k+1}最大\\ &1^\circ若c_{k+1}=b_{k+1}，这时候应该有\\ &a_1c_1+a_2c_2+...a_kc_k=a_1b_1+a_2b_2+...a_kb_k\\ &即\{a_{k+1}b_{k+1}\}也是满足使乘积和最大条件的一个序列（正序）\\ \\ &2^\circ 若c_{k+1}=\not b_{k+1}，设c_i=b_{k+1},(i=\not k+1且i\in N_+)，\\ &下面证明a_ic_{k+1}+a_{k+1}c_i\geq a_ic_i+a_{k+1}c_{k+1}：\\ &(即把c_i与c_{k+1}互换)\\ &a_ic_{k+1}+a_{k+1}c_i- (a_ic_i+a_{k+1}c_{k+1})=\\ &(a_i-a_{k+1})(c_{k+1}-c_i)\geq 0\\ &即若c_{k+1}=b_{k+1}也能是\{a_{k+1}c_{k+1}\}乘积最大\\ &结合1^\circ知n=k+1时也成立\\ &综上可得正序和\geq乱序和\\ &倒序和\leq乱序和同理 \end{aligned}$

阿贝尔变换：

（把求和变成另外一种容易比较大小的形式）

（图片来自百度百科）

排序不等式的两种证明方法