Weierstrass不等式的另一边 | Bernoulli不等式的推广

摘要: Bernoulli 不等式的变形，Weierstrass不等式的另一半

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在半年前的文章 Weierstrass不等式，概率方法的威力 中，我们以如下威尔斯特拉斯不等式为例，讨论了不等式证明中的概率方法：

Weierstrass不等式

设 $0 < a_{k} < 1, k=1,2,\cdots,n$，则：

$$1 - \sum\limits_{k=1}\limits^{n}a_{k} < \prod\limits_{k=1}\limits^{n}(1 - a_{k}) < \frac{1}{\prod\limits_{k=1}\limits^{n}(1 + a_{k})} < \frac{1}{1 + \sum\limits_{k=1}\limits^{n}a_{k}}$$

那篇文章中我只证明了以上不等式中的前两个不等号，本文我们证明第 3 个不等号，也就是 $\prod\limits_{k=1}\limits^{n}(1 + a_{k}) > 1 + \sum\limits_{k=1}\limits^{n}a_{k}$，事实上该不等式的成立条件可以放松，$a_{k} > -1$ 即可。

该不等式可以视为 Bernoulli 不等式 $(1 + x)^{n} \geq 1 + nx$ 的推广，Bernoulli 不等式非常基本，在算法分析中有很多应用案例，本文也略作介绍，以后再跟大家分享算法中的例子。

Bernoulli 不等式

若 $x \geq -1$，则：

• (1) 当 $0 < \alpha < 1$ 时，$(1 + x)^{\alpha} \leq 1 + \alpha x$
• (2) 当 $\alpha < 0$ 或 $\alpha > 1$ 时，$(1 + x)^{\alpha} \geq 1 + \alpha x$

仅当 $x = 0$ 时，等号成立。

证明（泰勒展开）

由 $(1 + x)^{\alpha}$ 在 $x_{0} = 0$ 处的带拉格朗日余项 $r_{n}(x) = \frac{f^{(n+1)}(\theta x)}{(n+1)!}x^{n+1}$ 的泰勒展开，其中 $\theta x$ 在 $x_{0}$ 和 $x$ 之间，即 $0 < \theta < 1$：

$$(1 + x)^{\alpha} = 1 + \alpha x + \frac{\alpha(\alpha - 1)}{2}x^{2}(1 + \theta x)^{\alpha - 2} \quad\quad 0 < \theta < 1$$

由于 $x \geq -1$，可得 $1 + \theta x > 0$。

考虑作差 $D = (1 + x)^{\alpha} - 1 - \alpha x = \frac{\alpha(\alpha - 1)}{2}x^{2}(1 + \theta x)^{\alpha - 2}$，其正负号就仅与 $\alpha(\alpha - 1)x^{2}$ 有关。

当 $x = 0$ 时 $D = 0$；当 $x \neq = 0$ 时，$D$ 的正负号即为 $\alpha(\alpha - 1)$ 的符号，当 $0 < \alpha < 1$，$\alpha(\alpha - 1) < 0$；当 $\alpha < 0$ 或 $\alpha > 1$，$\alpha(\alpha - 1) > 0$。

$\Box$

正整数指数的 Bernoulli 不等式

在算法分析这样的离散场景中，我们用的比较多的是 $\alpha = n \in \mathbb{N}^{* }$ 的情况，即 $(1 + x)^{n} \geq 1 + nx$，当 $n=1$ 或 $x = 0$ 时取等号。

Bernoulli 不等式的条件是 $x \geq -1$，而以上离散版本在 $x \geq -2$ 时也成立。下面是 $-2 \leq x < -1$ 情况的推导：

$$(1 + x)^{n} \geq - |1+x|^{n} \geq -|1+x| = 1 + x \geq 1 + nx$$

Weierstrass 不等式

下面我们证明 Weierstrass 不等式的第三个不等号，描述如下。

$x_{k} > -1$，$x_{k} \neq 0$ 且同号，$k=1,2,\cdots,n$，$n \geq 2$，则：

$$\prod\limits_{i=1}\limits^{n}(1 + x_{k}) > 1 + \sum\limits_{i=1}\limits^{n}x_{k}$$

证明（数学归纳法）

对 $n$ 用数学归纳法。

当 $n=2$ 时，$(1+x_{1})(1+x_{2}) = 1 + x_{1} + x_{2} + x_{1}x_{2}$，由于 $x_{k}\neq 0$ 且同号，$x_{1}x_{2} > 0$，$(1+x_{1})(1+x_{2}) > 1 + x_{1} + x_{2}$ 自然成立。

假设当 $n = N$ 时，不等式成立，即 $\prod\limits_{i=1}\limits^{N}(1 + x_{k}) > 1 + \sum\limits_{i=1}\limits^{N}x_{k}$。

下面考虑 $n = N + 1$ 的情况，$\prod\limits_{i=1}\limits^{N+1}(1 + x_{k}) = (1 + x_{N+1})\prod\limits_{i=1}\limits^{N}(1 + x_{k})$。

由于 $x_{k} > -1$，所以 $1 + x_{N+1} > 0$。于是：

$$\begin{align} (1 + x_{N+1})\prod\limits_{i=1}\limits^{N}(1 + x_{k}) &> (1 + x_{N+1})(1 + \sum\limits_{i=1}\limits^{N}x_{k}) \\ &= 1 + x_{N+1} + \sum\limits_{i=1}\limits^{N}x_{k} + x_{N+1}\sum\limits_{i=1}\limits^{N}x_{k} \end{align}$$

由于 $x_{k}, k=1,2,\cdots,N+1$ 均同号且不为 0，因此 $x_{N+1}$ 与 $\sum\limits_{i=1}\limits^{N}x_{k}$ 也同号且不为 0，因此 $x_{N+1}\sum\limits_{i=1}\limits^{N}x_{k} > 0$。

因此 $\prod\limits_{i=1}\limits^{N+1}(1 + x_{k}) > 1 + \sum\limits_{i=1}\limits^{N+1}x_{k}$。

$\Box$

该不等式可以视为正整数的 Bernoulli 不等式的推广，实际上令 $x_{1} = \cdots = x_{k} = x > -1$，代入后即得 $(1 + x)^{n} > 1 + nx$。

总结

不等式在算法方面的应用极多，算法分析中的大 O 符号是不等式，贪心算法的正确性证明中涉及到不等式，近似算法、随机算法涉及到的各种界是不等式。

此外最优化问题是不等式、极限是不等式、收敛是不等式，关于不等式的应用素材极多，此前写过很多相关的文章，在 不等式 标签下可以集中阅读，以后慢慢会持续跟大家分享。

---