递推数列：先证明收敛，再代极限

对

$$
x_{n+1}=f(x_n),
$$

按以下顺序处理：

  1. 解 $L=f(L)$，得到候选极限；
  2. 找不变区间 $I$，证明 $x_1\in I$ 且 $f(I)\subseteq I$；
  3. 用压缩映射或单调有界证明收敛；
  4. 最后在递推式两边取极限，确定 $L$。

$L=f(L)$ 只给候选值，不能证明极限存在。若不动点不止一个，初值和不变区间决定可能趋向哪一个。

压缩映射

若在不变区间 $I$ 上有统一常数 $q<1$，满足

$$
|f’(x)|\le q,\qquad x\in I,
$$

则

$$
0\leqslant|x_{n+1}-L|
\le q|x_n-L|
\le q^n|x_1-L|\to0.
$$

不能只写逐点的 $|f’(x)|<1$；要说明作用区间，并给出统一上界 $q$。

若 $|f’(L)|>1$，该不动点通常不稳定；若 $|f’(L)|=1$，一阶判据不能决定收敛性。

单调有界

单调性

  • 作差：判断 $x_{n+1}-x_n$；
  • 正项数列作商：比较 $x_{n+1}/x_n$ 与 $1$；
  • 递推式：判断 $f(x)-x$ 在不变区间上的符号；
  • 若 $x_n=g(n)$：研究 $g’(x)$。

若 $f$ 递增，$x_2\ge x_1$ 可通过

$$
x_{n+1}=f(x_n)\ge f(x_{n-1})=x_n
$$

归纳传递。若 $f$ 递减，数列可能交替振荡，应分别研究奇偶子列，或改看 $f\circ f$。

有界性

  • 猜出界后用归纳法；
  • 证明区间 $I$ 在 $f$ 下保持不变；
  • 已知递增只需找上界，已知递减只需找下界。

隐式定义的数列

若 $x_n$ 是 $F(x)=n$ 在某区间内的唯一解，且 $F$ 严格单调，则

$$
x_n=F^{-1}(n).
$$

$F$ 递增时 $x_n$ 递增；$F$ 递减时 $x_n$ 递减。研究增长速度时，将 $n=F(x_n)$ 与 $F$ 的主导项比较。

使用逆函数前必须确认：解存在、解唯一、$F$ 的单调区间正确。

两个数列共同递推

遇到 $a_{n+1},b_{n+1}$ 由 $a_n,b_n$ 共同决定时，先找结构：

  • $a_n\le b_n$ 是否保持；
  • 和、积或其他组合是否不变；
  • 是否一列递增、另一列递减；
  • 差值是否收缩：
    $$|a_{n+1}-b_{n+1}|\le q|a_n-b_n|,　q<1.$$

若 $a_n$ 递增、$b_n$ 递减、$a_n\le b_n$，且 $b_n-a_n\to0$，则两列趋于同一极限。