跳转至

递推的界与单调性怎样建立？

先备知识

单调有界定理是一张收敛证书，但递推式通常不会直接把“单调”“有界”写在表面。必须先用数学归纳法证明一个不变区间，再在该区间内比较相邻项。只有收敛已经得到后，才可以把极限传入递推关系求其数值。

学习目标

完成本单元后，你应能：

  1. 用归纳法证明递推的不变区间；
  2. 在不变区间内证明递推数列的单调性；
  3. 按“区间—单调—收敛—不动点方程”的顺序组织证明；
  4. 用振荡反例否定“有代数候选就必收敛”。

牵引问题

从 \(x_1=1\) 出发反复计算

\[ x_{n+1}=\sqrt{2+x_n}, \]

计算器会显示数值靠近 \(2\)。怎样把有限次观察升级为覆盖所有 \(n\) 的证明？

探索与猜想

若 \(1\le x_n\le2\)，则 \(3\le2+x_n\le4\)，从而下一项仍在 \([1,2]\)。这个区间既控制平方根有定义，也让

\[ x_{n+1}\ge x_n \quad\Longleftrightarrow\quad 2+x_n\ge x_n^2 \]

成为可验证的不等式。先把这些事实做成证书，再谈极限方程。

概念与理论

命题：不变区间

由 \(x_1=1\) 与 \(x_{n+1}=\sqrt{2+x_n}\) 定义的数列满足

\[ 1\le x_n\le2\qquad(n\in\mathbb N). \]

证明。 对命题 \(P(n):1\le x_n\le2\) 作归纳。

初始步：\(x_1=1\)，所以 \(P(1)\) 成立。

归纳步：假设 \(P(n)\) 成立，则 \(1\le x_n\le2\)，因而

\[ 3\le2+x_n\le4. \]

平方根在非负数上保持次序，于是

\[ \sqrt3\le x_{n+1}=\sqrt{2+x_n}\le2. \]

特别地 \(1\le x_{n+1}\le2\)，故 \(P(n+1)\) 成立。由归纳法，结论对所有 \(n\) 成立。\(\square\)

命题：单调性

上述数列递增。

证明。 已知 \(x_n\in[1,2]\)，所以 \(x_n\) 与 \(x_{n+1}\) 都非负，可以安全平方。于是

\[ \begin{aligned} x_{n+1}\ge x_n &\Longleftrightarrow 2+x_n\ge x_n^2\\ &\Longleftrightarrow (2-x_n)(x_n+1)\ge0. \end{aligned} \]

其中 \(2-x_n\ge0\) 且 \(x_n+1>0\)，故乘积非负。因此对每个 \(n\) 都有 \(x_{n+1}\ge x_n\)。\(\square\)

引理：移位数列保持原极限

若 \(x_n\to L\)，则 \(x_{n+1}\to L\)。

证明。 给定 \(\varepsilon>0\)。由 \(x_n\to L\)，存在 \(N\in\mathbb N\)，使每当 \(k\ge N\) 时都有 \(|x_k-L|<\varepsilon\)。若 \(n\ge N\)，则 \(n+1\ge N\)，把 \(k=n+1\) 代入便得

\[ |x_{n+1}-L|<\varepsilon. \]

这正是 \(x_{n+1}\to L\) 的 \(\varepsilon\)--\(N\) 定义。\(\square\)

收敛之后才解不动点方程

由前两个命题，\((x_n)\) 递增且以上界 \(2\) 控制，所以单调有界定理给出某个 \(L\in[1,2]\) 使 \(x_n\to L\)。由移位引理，\(x_{n+1}\to L\)。再使用恒等式

\[ x_{n+1}^2=2+x_n \]

结合极限运算法则给出 \(L^2=2+L\)。因此

\[ (L-2)(L+1)=0. \]

代数候选是 \(2\) 与 \(-1\)，但区间证书 \(L\in[1,2]\) 排除 \(-1\)，故 \(L=2\)。注意逻辑顺序：不动点方程在这里用于识别已经证明存在的极限，不负责制造收敛性。

例题与迁移

例题 1：有限计算怎样服务于证明

下面的程序生成前几项并检查样本是否仍在 \([1,2]\) 且非递减：

from math import sqrt

x = 1.0
values = [x]
for _ in range(7):
    x = sqrt(2 + x)
    values.append(x)

assert all(1 <= value <= 2 for value in values)
assert all(left <= right for left, right in zip(values, values[1:]))
print(values)

程序适合发现猜想或检查实现，却只覆盖有限项。覆盖所有指标的证据仍是上面的两个归纳/不等式证明。

例题 2：有不动点候选但数列振荡

令 \(x_1=0\)，\(x_{n+1}=1-x_n\)。不动点方程

\[ L=1-L \]

有唯一候选 \(L=1/2\)。然而递推直接给出 \(x_n=0\)（\(n\) 为奇数）和 \(x_n=1\)（\(n\) 为偶数），所以每一项到 \(1/2\) 的距离都等于 \(1/2\)。取 \(\varepsilon=1/4\)，不存在任何 \(N\) 使 \(n\ge N\) 时 \(|x_n-1/2|<\varepsilon\)。数列不收敛。代数候选存在绝不能等同于收敛。

即时检验与回望

  1. 在平方 \(x_{n+1}\ge x_n\) 之前，为什么必须先建立不变区间？
答案

平方不总保持实数大小关系；只有先知道两边非负，才能把 \(x_{n+1}\ge x_n\) 等价改写成 \(x_{n+1}^2\ge x_n^2\)。不变区间提供了这个符号条件，同时给出最后所需的上界。

  1. 若某递推的不动点方程只有一个实根，是否已经证明递推数列收敛？
答案

没有。不动点方程只说明“若极限存在，它必须是什么”。递推 \(x_{n+1}=1-x_n\) 的方程只有根 \(1/2\)，但从 \(x_1=0\) 出发仍在 \(0\) 与 \(1\) 之间振荡。

习题与答案

习题 1：补全归纳步

在主例中，为什么从 \(\sqrt3\le x_{n+1}\le2\) 可以推出归纳目标 \(1\le x_{n+1}\le2\)？

答案

因为 \(\sqrt3>1\)，故 \(\sqrt3\le x_{n+1}\) 蕴含 \(1\le x_{n+1}\)；上界已经是 \(x_{n+1}\le2\)。所以合起来正是 \(P(n+1)\)。

习题 2：线性递推的不变量

令 \(y_1=0\)，\(y_{n+1}=(y_n+2)/2\)。用归纳法证明 \(0\le y_n\le2\)。

答案

初始时 \(y_1=0\in[0,2]\)。若 \(0\le y_n\le2\)，则 \(2\le y_n+2\le4\)，除以正数 \(2\) 得 \(1\le y_{n+1}\le2\)，特别地 \(0\le y_{n+1}\le2\)。归纳法完成证明。

习题 3：线性递推的单调与极限

继续上题，证明 \((y_n)\) 递增并求其极限。

答案

由不变量 \(y_n\le2\)，

\[ y_{n+1}-y_n=\frac{2-y_n}{2}\ge0, \]

故数列递增，又以上界 \(2\) 控制，所以收敛。设极限为 \(L\)，将极限传入 \(y_{n+1}=(y_n+2)/2\) 得 \(L=(L+2)/2\)，从而 \(L=2\)。

习题 4：振荡例的其他初值

对 \(x_{n+1}=1-x_n\)，证明只有初值 \(x_1=1/2\) 会产生收敛数列。

答案

递推两次得 \(x_{n+2}=1-x_{n+1}=x_n\)，所以奇数项恒为 \(x_1\)，偶数项恒为 \(1-x_1\)。若数列收敛到 \(L\)，则由上面的移位引理，\(x_{n+1}\to L\)；再由差法则，

\[ x_{n+1}-x_n\to L-L=0. \]

另一方面，递推式给出 \(|x_{n+1}-x_n|=|1-2x_n|=|1-2x_1|\)，其中最后一步利用奇偶项交换但绝对差不变。若这个常数为正，取其一半为 \(\varepsilon\)，相邻差便不可能趋于 \(0\)；故 \(|1-2x_1|=0\)，即 \(x_1=1/2\)。反之，若 \(x_1=1/2\)，则每一项都等于 \(1/2\)，当然收敛。

习题 5：审查错误顺序

有人对主例写道：“解 \(L=\sqrt{2+L}\) 得 \(L=2\)，所以 \(x_n\to2\)。”指出两个缺口并给出正确顺序。

答案

第一，方程只对已经存在的极限成立，原推理没有证明收敛。第二，平方后的方程还有候选 \(-1\)，必须用区间信息排除。正确顺序是：归纳证明 \([1,2]\) 不变；在该区间证明递增；由单调有界定理证明极限 \(L\) 存在；最后传递极限并用 \(L\in[1,2]\) 选出 \(L=2\)。

常见误区与后续

  • 归纳只写传递步。 没有初始步，不变量没有起点。
  • 在符号未知时平方不等式。 先用不变区间确定非负性。
  • 把数值表当作全体证明。 程序只能检查已生成的有限项。
  • 先解不动点再宣告收敛。 必须先证明收敛，再由方程识别极限。下一单元将把“目标始终被闭区间包住”发展成另一类完备性证书。