OI中你可能会用到的一些不等式及其证明

# 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} $$ $d_1, d_2, \cdots , d_n$ 是 1\~n 的任意一个排列 取等条件：$a_1=a_2=\cdots = a_n$ **或者** $b_1=b_2=\cdots = b_n$ ### Extra: （补充的可以作为了解的几个不等式） #### 杨氏 (Young) 不等式 $a,b\ge 0,p>1,\frac 1p+\frac 1q=1$，有 $$ ab\le \frac {a^p}p +\frac {b^q}q $$ 取等条件：$a^p=b^q$ #### 赫尔德 (Holder) 不等式 $a_i,b_i\ge 0,p>1,\frac 1p + \frac 1q=1$，有 $$ \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)$ 也成立 整理一下现在的条件，我们有 $P(1),P(2)$ 成立，$P(n)$ 成立时 $P(2n)$ 成立，$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$ $H_n\le G_n\le A_n\le Q_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(1)$ 显然成立 $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} $$ $d_1, d_2, \cdots , d_n$ 是 $1\sim n$ 的任意一个排列 我们使用数学归纳法证明： 我们用 $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 ](http://poj.org/problem?id=3544) （排序不等式） [CF163D Large Refrigerator](https://www.luogu.com.cn/problem/CF163D) (均值不等式) [CF1401D Maximum Distributed Tree](https://www.luogu.com.cn/problem/CF1401D) (排序不等式) [P2647 最大收益](https://www.luogu.com.cn/problem/P2647) (排序不等式) 牛客小白月赛5-B-范围(range)（柯西不等式） 柯西不等式的证明参考了 [河西学院数学系论文](https://ishare.iask.sina.com.cn/f/36849309.html) 排序不等式的证明参考了 [一位大神的Blog](https://blog.csdn.net/Balbooa/article/details/79474829) $$ \texttt{Thanks for reading} $$