夹逼定理加放缩法，将和式放缩为最值

摘要: 夹逼定理+放缩法

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

---

在文章 由p范数诱导的距离，当p趋于无穷时为切比雪夫距离 中，我们主要证明了 p 范数诱导的距离当 $p \rightarrow\infty$ 时为切比雪夫距离。

证明过程用到了洛必达法则，复合函数求导法则，指数函数的导数等微积分的结论。后来一位群友提出了用夹逼定理会更优雅，并且给出了放缩的思路。

我一看发现确实可以，而且只用了夹逼定理，没有用到微积分的其它结论，且过程更加简洁。这种放缩应该是一种通用的思路，在处理将和式转换为最值的问题时可以考虑。

下面将这位群友的思路分享给各位。

结论

在 p 范数中，当 $p \rightarrow\infty$ 时，其诱导出的距离，也就是 $\infty$ 范数距离，正是切比雪夫距离，也就是：

$$\lim\limits_{p\rightarrow +\infty} \left( \sum\limits_{i=1}\limits^{n} |x_{i} - y_{i}|^{p} \right)^{1/p} = \max\limits_{1 \leq i\leq n} |x_{i} - y_{i}|$$

证明 (放缩法+夹逼定理)

考虑和式 $S_{n} = \sum\limits_{i=1}\limits^{n}a_{i}$，其中各个项均非负，即 $a_{i} \geq 0$。

假设各个项中的最大值为 $a_{k} = \max\limits_{1 \leq i \leq n} a_{i}$，那么将各个项均改成 $a_{k}$，所得的结果自然大于 $S_{n}$，也就是 $S_{n} \leq na_{k}$，即：

$$\sum\limits_{i=1}\limits^{n}a_{i} \leq n\max\limits_{1 \leq i \leq n} a_{i}$$

将和式中原有的最大值的项 $a_{k}$ 保留，其余的均改为 0，所得的结果自然小于 $S_{n}$，也就是 $a_{k} \leq S_{n}$，即：

$$\max\limits_{1 \leq i \leq n} a_{i} \leq \sum\limits_{i=1}\limits^{n}a_{i}$$

上面两个显然的不等式就是我们放缩的基础。可以看到经过上面两步放缩之后，原本的和式变成了最值。

代入到本题的情况，即 $a_{i} = |x_{i} - y_{i}|^{p}$，这里显然满足 $a_{i} \geq 0$，于是有：

$$\max\limits_{1 \leq i \leq n} |x_{i} - y_{i}|^{p} \leq \sum\limits_{i=1}\limits^{n} |x_{i} - y_{i}|^{p} \leq n\max\limits_{1 \leq i \leq n} |x_{i} - y_{i}|^{p}$$

令 $\max\limits_{1\leq i \leq n}|x_{i} - y_{i}|^{p} = |x_{k} - y_{k}|^{p}$，并上式同时进行 $\frac{1}{p}$ 次的乘方，得到：

$$|x_{k} - y_{k}| \leq (\sum\limits_{i=1}\limits^{n} |x_{i} - y_{i}|^{p})^{\frac{1}{p}} \leq n^{\frac{1}{p}}|x_{k} - y_{k}|$$

上式最左边是一个常数 $|x_{k} - y_{k}|$，因此当 $p\rightarrow +\infty$ 时，极限还是它自己。

上式最右边是一个常数 $|x_{k} - y_{k}|$ 乘以一个函数 $n^{\frac{1}{p}}$，由于 $\lim\limits_{p\rightarrow +\infty}n^{\frac{1}{p}} = 1$，因此当 $p\rightarrow +\infty$ 时，右边的极限依然是 $|x_{k} - y_{k}|$。

于是由夹逼定理，当 $p\rightarrow +\infty$ 时，中间项的极限也是 $|x_{k} - y_{k}|$，即：

$$\lim\limits_{p\rightarrow +\infty} \left( \sum\limits_{i=1}\limits^{n} |x_{i} - y_{i}|^{p} \right)^{1/p} = \max\limits_{1 \leq i\leq n} |x_{i} - y_{i}|$$

夹逼定理

函数 $f, g, h$ 在 $x_{0}$ 附近满足 $g(x) \leq f(x) \leq h(x)$，且 $\lim\limits_{x\rightarrow x_{0}}g(x) = \lim\limits_{x\rightarrow x_{0}}h(x) = a$，则有 $\lim\limits_{x\rightarrow x_{0}}f(x) = a$。

$\Box$

---