0xff

本文分为 3 部分，

第 1 部分是介绍这些不等式，第 2 部分是证明这些不等式，第 3 部分为小量习题和参考资料

本文整理了一些 OI 中迟早会用到的不等式，本文中的所有证明均只用到初等（甚至初中）数学内容，所以放心吔。

\sum_{i=l}^{r}a_i=a_l+a_{l+1}+\cdots + a_{r-1}+a_r

这里的 a_i,b_i 啥全部在实数域内

可爱的不等式们

均值不等式：

a_i\ge 0

平方平均数：Q_n=\sqrt {\frac {\sum _{i=1}^na^2_i}{n}}

算术平均数：A_n=\frac {\sum_{i=1}^na_i}n

几何平均数：G_n=\sqrt[n]{a_1a_2\cdots a_n}

调和平均数：H_n=\frac n {\sum_{i=1}^n\frac {1}{a_i}}

他们之间的关系：H_n\le G_n\le A_n\le Q_n，简称”调几算方“

取等条件（即 Q_n=A_n=G_n=H_n）：a_1=a_2=\cdots=a_n

柯西 (Cauchy)不等式

(\sum_{i=1}^na_i^2)\times (\sum_{i=1}^nb_i^2)\ge (\sum _{i=1}^na_ib_i)^2

取等条件：\frac {a_1}{b_1}=\frac {a_2}{b_2}=\cdots = \frac {a_n}{b_n} ，或者 a_1=a_2=\cdots =a_n=0 ，或者 b_1=b_2=\cdots = b_n=0

排序不等式

设 a_1\le a_2\le \cdots \le a_n , b_1\le b_2\le \cdots \le b_n

\sum_{i=1}^na_ib_{n-i+1}\le \sum_{i=1}^na_ib_{d_i}\le \sum _{i=1}^n{a_ib_i} 取等条件：$a_1=a_2=\cdots = a_n$ **或者** $b_1=b_2=\cdots = b_n

Extra: （补充的可以作为了解的几个不等式）

杨氏 (Young) 不等式

$$ ab\le \frac {a^p}p +\frac {b^q}q $$ 取等条件：$a^p=b^q

赫尔德 (Holder) 不等式

$$ \sum_{i=1}^n a_ib_i\le \sqrt[p]{\sum _{i=1}^na^p_i}\times \sqrt[q]{{\sum_{i=1}^n}b_i^q} $$ 取等条件：$\frac {a_1^p}{b_1^q}=\frac {a_2^p}{b^2_q}=\cdots = \frac {a^p_n}{b^q_n}$，或者 $a_1=a_2=\cdots =a_n=0$ ，或者 $b_1=b_2=\cdots = b_n=0

证明

均值不等式：

首先来证 A_n\le Q_n，即 \frac {\sum_{i=1}^na_i}n\le \sqrt {\frac {\sum _{i=1}^na^2_i}{n}}

(c-d)^2\ge 0 c^2-2cd+d^2\ge 0 c^2+d^2\ge 2cd

那么我们来看这个柿子：

\sum_{1\le i,j\le n,i\ne j} {2a_ia_j} \le (n-1)\times \sum _{i=1}^n a_i^2

我们发现，左边展开有 \frac {n(n-1)}2 项，右边展开有 n(n-1) 项

那么左边的每一个 2a_ia_j 都可以在右边找到一个对应的 a_i^2,a_j^2 ，所以这个柿子成立

然后继续添加一点东西

\sum_{1\le i,j\le n,i\ne j} {2a_ia_j} +\sum _{i=1}^n a_i^2\le n\times \sum _{i=1}^n a_i^2 (\sum_{i=1}^na_i)^2\le n\times \sum _{i=1}^n a_i^2 \frac {(\sum_{i=1}^na_i)^2}{n^2}\le \frac {\sum _{i=1}^n a_i^2}{n} \frac {\sum_{i=1}^na_i}{n}\le \sqrt{\frac {\sum _{i=1}^n a_i^2}{n}}

即证明了 A_n\le Q_n

接下来来证明均值不等式中最经典的 G_n\le A_n，即 \sqrt[n]{a_1a_2\cdots a_n}\le \frac {\sum_{i=1}^na_i}n

使用数学归纳法

我们用 P(n) 表示 \sqrt[n]{a_1a_2\cdots a_n}\le \frac {\sum_{i=1}^na_i}n 这个命题

因为 a_1=a_1 ，所以 P(1) 成立

因为

(\frac {c+d}2)^2-cd = \frac {c^2+2cd+d^2}{4}-cd =\frac {c^2-2cd+d^2}{4}=\frac{(c-d)^2}{4}

因为

(c-d)^2 \ge 0

所以

\frac{(c-d)^2}{4} \ge 0

所以

(\frac {c+d}2)^2 \ge cd

所以

\frac {c+d}2 \ge \sqrt{cd}

所以 P(2) 成立

假设 P(n) 成立

设 c_1=\frac {a_1+a_2+\cdots +a_n}{n} , c_2=\frac{a_{n+1}+a_{n+2}+\cdots +a_{2n}}{n} , d_1=\sqrt[n]{a_1a_2\cdots a_n} , d_2=\sqrt[n]{a_{n+1}a_{n+2}\cdots a_{2n}}

根据 P(2) 成立，我们可以推出

\frac {c_1+c_2}{2} \ge \sqrt{d_1d_2}

根据 P(n) 成立，我们推出

c_1 \ge d_1,c_2\ge d_2

这里，你只要稍微想一想，假设 c_1=d_1,c_2=d_2 ，那么 \frac {c_1+c_2}{2} \ge \sqrt{d_1d_2}

而，c_1,c_2 却是 \ge d_1,d_2 ，那还用说，\frac {c_1+c_2}{2} \ge \sqrt{d_1d_2} 肯定成立

那么，

\frac {c_1+c_2}{2}\ge \sqrt{d_1d_2} \frac {\frac {a_1+a_2+\cdots +a_n}{n}+\frac{a_{n+1}+a_{n+2}+\cdots +a_{2n}}{n}}{2}\ge \sqrt{\sqrt[n]{a_1a_2\cdots a_n} \times \sqrt[n]{a_{n+1}a_{n+2}\cdots a_{2n}}} \frac {\frac {a_1+a_2+...+a_{2n}}{n}}{2}\ge \sqrt{\sqrt[n]{a_1a_2...a_{2n}}} \frac {a_1+a_2+...+a_{2n}}{2n}\ge \sqrt[2n]{a_1a_2...a_{2n}}

于是，我们可以通过 P(n) 成立来推出 P(2n) 成立

于是，对于任意的 P(2^k)，都成立

接下来，我们要通过 P(n) 成立来推出 P(n-1) 成立：

假设 P(n) 成立：

我们先想一下，要找一个 a_n 使得 \frac {a_1+a_2+\cdots +a_n}{n}=\frac {a_1+a_2+\cdots +a_{n-1}}{n-1}

\frac {a_1+a_2+\cdots +a_n}{n}=\frac {a_1+a_2+\cdots +a_{n-1}}{n-1} (n-1) \times (a_1+a_2+\cdots +a_n)=n \times (a_1+a_2+\cdots +a_{n-1}) (n-1) \times (a_1+a_2+\cdots +a_{n-1})+(n-1) \times a_n=(n-1) \times (a_1+a_2+\cdots +a_{n-1})+(a_1+\cdots +a_{n-1}) (n-1) \times a_n=(a_1+a_2+\cdots +a_{n-1}) a_n=\frac {a_1+a_2+\cdots +a_{n-1}}{n-1}

于是，这里 \frac {a_1+a_2+\cdots +a_n}{n}=\frac {a_1+a_2+\cdots +a_{n-1}}{n-1}

那么就有：

\frac {a_1+a_2+\cdots +a_{n-1}}{n-1} \ge \sqrt[n]{a_1a_2\cdots a_n}

两边同时 n-1 次方

(\frac {a_1+a_2+...+a_{n-1}}{n-1})^n \ge a_1a_2...a_n

把 a_n 代入

(\frac {a_1+a_2+\cdots +a_{n-1}}{n-1})^n \ge a_1a_2\cdots a_{n-1} \times \frac {a_1+a_2+\cdots +a_{n-1}}{n-1} (\frac {a_1+a_2+\cdots +a_{n-1}}{n-1})^{n-1} \ge a_1a_2\cdots a_{n-1}

两边同时开 n 次根号

\frac {a_1+a_2+\cdots +a_{n-1}}{n-1} \ge \sqrt[n-1]{a_1a_2\cdots a_{n-1}}

于是当 P(n) 成立时 P(n-1) 也成立

整理一下现在的条件，我们有

于是，对于任何正整数 $n$ ， $P(n)$ 都成立 于是证明了 $G_n\le A_n

最后一个，H_n\le G_n ，即 \frac n {\sum_{i=1}^n\frac {1}{a_i}}\le \sqrt[n]{a_1a_2\cdots a_n}，a_i\ge 0

我们先把刚证的 G_n\le A_n 拿过来

\sqrt[n]{a_1a_2\cdots a_n}\le \frac {\sum_{i=1}^na_i}n

我们把所有的 a_i=\frac 1{a_i}，替换一下

即

\sqrt[n]{\frac 1{a_1a_2\cdots a_n}}\le \frac {\sum_{i=1}^n\frac 1{a_i}}n

两边同时取倒数，又因为两边同号，所以不等号取反

\frac 1{\sqrt[n]{\frac 1{a_1a_2\cdots a_n}}}\ge \frac n{\sum_{i=1}^n\frac 1{a_i}} ((\frac 1{a_1a_2\cdots a_n})^{\frac 1n})^{-1}\ge \frac n{\sum_{i=1}^n\frac 1{a_i}} ((\frac 1{a_1a_2\cdots a_n})^{-1})^{\frac 1n}\ge \frac n{\sum_{i=1}^n\frac 1{a_i}} (a_1a_2\cdots a_n)^{\frac 1n}\ge \frac n{\sum_{i=1}^n\frac 1{a_i}} \sqrt[n]{a_1a_2\cdots a_n)}\ge \frac n{\sum_{i=1}^n\frac 1{a_i}}

即 H_n\le G_n

关于取等条件，我们发现上面都用到了 $(c-d)^2\ge 0$ 这个，那么 $(c-d)^2=0$ 的时候就是 $c=d

所以取等条件是 a_1=a_2=\cdots=a_n

柯西 (Cauchy)不等式

(\sum_{i=1}^na_i^2)\times (\sum_{i=1}^nb_i^2)\ge (\sum _{i=1}^na_ib_i)^2

在人教版选修4-5上有一种通过巧妙地构造来证明的方法

f(x)=\sum_{i=1}^n(a_ix+b_i)^2 =(\sum_{i=1}^na_i^2)x^2+2(\sum_{i=1}^na_ib_i)+\sum_{i=1}^nb_i^2\ge 0

所以 f(x) 的判别式 \Delta \le 0

所以

(2(\sum_{i=1}^na_ib_i))^2-4((\sum_{i=1}^na_i^2)\times (\sum_{i=1}^nb_i^2))\le 0 4(\sum_{i=1}^na_ib_i)^2\le4((\sum_{i=1}^na_i^2)\times (\sum_{i=1}^nb_i^2)) (\sum_{i=1}^na_i^2)\times (\sum_{i=1}^nb_i^2)\ge(\sum_{i=1}^na_ib_i)^2

当 \Delta=0 时，上面的 \ge 变成 = ，那么方程的 2 实数根相等，也就是说 x 唯一

那么就有 a_1x+b_1=a_2x+b_2=\cdots =a_nx+b_n=0

若 x=0 ，那么 b_1=b_2=\cdots = b_n=0

若 x\ne 0 ，那么 a_x=-\frac 1xb_i，那么 \frac {a_1}{b_1}=\frac {a_2}{b_2}=\cdots = \frac {a_n}{b_n}

交换 a_i,b_i 就可得到：

取等条件：\frac {a_1}{b_1}=\frac {a_2}{b_2}=\cdots = \frac {a_n}{b_n} ，或者 a_1=a_2=\cdots =a_n=0 ，或者 b_1=b_2=\cdots = b_n=0

当然也可以用数学归纳法：

我们用 P(n) 表示 (\sum_{i=1}^na_i^2)\times (\sum_{i=1}^nb_i^2)\ge (\sum _{i=1}^na_ib_i)^2 这个命题

$P(2)$ 随便推推： $$ (a^2+b^2)(c^2+d^2)=(ac)^2+(bd)^2+(bc)^2+(ad)^2 $$ $$ =(ac)^2+2abcd+(bd)^2+(bc)^2-2abcd+(ad)^2 $$ $$ =(ac+bd)^2-(bc-ad)^2\ge (ac+bd)^2 $$ 取等条件 $bc-ad=0$，即 $\frac ac=\frac bd

那么我们现在要从 P(n) 成立推到 P(n+1)

假设 P(n) 成立：即 (\sum_{i=1}^na_i^2)\times (\sum_{i=1}^nb_i^2)\ge (\sum _{i=1}^na_ib_i)^2

(\sum_{i=1}^na_i^2+a_{n+1}^2)\times (\sum_{i=1}^nb_i^2+b_{n+1}^2)=(\sum_{i=1}^na_i^2)\times (\sum_{i=1}^nb_i^2)+(\sum_{i=1}^na_i^2)\times b_{n+1}^2+(\sum_{i=1}^nb_i^2)\times a_{n+1}^2+a_{n+1}^2b_{n+1}^2

其中

因为

(AD^2-BC^2)\ge0 A^2D^4-2ABC^2D^2+B^2C^4\ge 0 A^2D^4+2ABC^2D^2+B^2C^4\ge 4ABC^2D^2 (AD^2+BC^2)^2\ge 4ABC^2D^2 AD^2+BC^2\ge \sqrt{4ABC^2D^2} A\times D^2+B\times C^2\ge 2\times |C|\times |D|\times \sqrt{AB}

代入 A=\sum_{i=1}^na_i^2,B=\sum_{i=1}^nb_i^2,C=a_{n+1}^2,D=b_{n+1}^2，得

(\sum_{i=1}^na_i^2)\times b_{n+1}^2+(\sum_{i=1}^nb_i^2)\times a_{n+1}^2\ge2\times |a_{n+1}|\times |b_{n+1}|\times \sqrt{(\sum_{i=1}^na_i^2)\times (\sum_{i=1}^nb_i^2)}

因为 (\sum_{i=1}^na_i^2)\times (\sum_{i=1}^nb_i^2)\ge (\sum _{i=1}^na_ib_i)^2，所以 \sqrt{(\sum_{i=1}^na_i^2)\times (\sum_{i=1}^nb_i^2)}\ge (\sum _{i=1}^na_ib_i)，

又因 |a_{n+1}|\times |b_{n+1}|\ge a_{n+1}\times b_{n+1}

所以

(\sum_{i=1}^na_i^2)\times b_{n+1}^2+(\sum_{i=1}^nb_i^2)\times a_{n+1}^2\ge 2\times a_{n+1}\times b_{n+1}\times (\sum _{i=1}^na_ib_i)

所以

(\sum_{i=1}^na_i^2)\times (\sum_{i=1}^nb_i^2)+(\sum_{i=1}^na_i^2)\times b_{n+1}^2+(\sum_{i=1}^nb_i^2)\times a_{n+1}^2+a_{n+1}^2b_{n+1}^2 \ge(\sum _{i=1}^na_ib_i)^2+2\times a_{n+1}\times b_{n+1}\times (\sum _{i=1}^na_ib_i)+a_{n+1}^2b_{n+1}^2

所以

(\sum_{i=1}^na_i^2+a_{n+1}^2)\times (\sum_{i=1}^nb_i^2+b_{n+1}^2)\ge (\sum _{i=1}^{n+1}a_ib_i)^2

所以 P(n+1) 成立

由此通过数学归纳法证明了柯西不等式

排序不等式

设 a_1\le a_2\le \cdots \le a_n , b_1\le b_2\le \cdots \le b_n

\sum_{i=1}^na_ib_{n-i+1}\le \sum_{i=1}^na_ib_{d_i}\le \sum _{i=1}^n{a_ib_i} 我们使用数学归纳法证明： 我们用 $P(n)$ 表示 $\sum_{i=1}^na_ib_{n-i+1}\le \sum_{i=1}^na_ib_{d_i}\le \sum _{i=1}^n{a_ib_i}$ 这个命题 显然 $P(1)$ 和 $P(2)$ 成立 我们现在要通过 $P(n)$ 推出 $P(n+1)$ 成立： 假设 $P(n)$ 成立，即 $\sum_{i=1}^na_ib_{n-i+1}\le \sum_{i=1}^na_ib_{d_i}\le \sum _{i=1}^n{a_ib_i}

那么有

\sum _{i=1}^n{a_ib_i}+a_{n+1}b_{n+1}\ge\sum_{i=1}^na_ib_{d_i}+a_{n+1}b_{n+1}

即

\sum _{i=1}^{n+1}{a_ib_i}\ge\sum_{i=1}^na_ib_{d_i}+a_{n+1}b_{n+1}

我们可以把右边的 n+1 和 d_1,\cdots,d_n 中任何一个交换，也可以不动，所以给原来 n! 的全排列乘上了 n+1 种方案数，那么就变成了 (n+1)! ，于是 \sum _{i=1}^{n+1}{a_ib_i}\ge\sum_{i=1}^{n+1}a_ib_{d_i} 成立

同理，有

\sum _{i=1}^n{a_ib_{n-i+1}}+a_{n+1}b_{n+1}\le\sum_{i=1}^na_ib_{d_i}+a_{n+1}b_{n+1}

即

\sum _{i=1}^{n+1}{a_ib_{n-i+1}}\le\sum_{i=1}^na_ib_{d_i}+a_{n+1}b_{n+1}

我们可以把右边的 n+1 和 d_1,\cdots,d_n 中任何一个交换，也可以不动，所以给原来 n! 的全排列乘上了 n+1 种方案数，那么就变成了 (n+1)! ，于是 \sum_{i=1}^{n+1}a_ib_{n-i+1}\le \sum_{i=1}^{n+1}a_ib_{d_i} 成立

所以我们通过 P(n) 成立证明了 P(n+1) 成立

由此证明了排序不等式

习题以及参考资料

题都很水

poj 3544 Journey with Pigs （排序不等式）

CF163D Large Refrigerator (均值不等式)

CF1401D Maximum Distributed Tree (排序不等式)

P2647 最大收益 (排序不等式)

牛客小白月赛5-B-范围(range)（柯西不等式）

柯西不等式的证明参考了 河西学院数学系论文

排序不等式的证明参考了 一位大神的Blog

\texttt{Thanks for reading}