递推数列

这一招在做什么

$k$ 阶递推数列的每一项由前 $k$ 项确定。最常见、也最有章法的是常系数线性递推

a_{n + 2} = p a_{n + 1} + q a_{n} .

关键观察：如果 $λ^{n}$ 这样的等比数列满足递推，那么 $λ^{n + 2} = p λ^{n + 1} + q λ^{n}$ ，即

λ^{2} = p λ + q (特征方程) .

而且满足递推的数列可以任意线性组合。于是：

写出特征方程，求出特征根 $λ_{1}, λ_{2}$ 。
两根不等时设 $a_{n} = A λ_{1}^{n} + B λ_{2}^{n}$ ；两根相等时设 $a_{n} = (A + B n) λ^{n}$ 。
用两个初值列方程，解出 $A, B$ ；再代回去验算。

先猜后证

$a_{0} = 1, a_{1} = 3, a_{n + 2} = 3 a_{n + 1} - 2 a_{n}$ 。求 $a_{10}$ 。

先选定答案，才能看到结论。

跟着做一遍

例：a₀ = 1, a₁ = 4, a_{n+2} = 5a_{n+1} − 6aₙ

第 1 / 5 步

先算几项
$1, 4, 14, 46, 146, \dots$ 增长得很快。“比值”一列越来越接近 $3$ ——这是在提示：数列的“主体”是 $3^{n}$ 。

$a_{2} = 5 \cdot 4 - 6 \cdot 1 = 14$
特征方程
通项的形式
用初值定系数
验算

一阶的情形：减去不动点

$a_{n + 1} = p a_{n} + r$ （ $p \neq = 1$ ）不是等比数列，但差一个常数就是。找不动点 $x^{*} = p x^{*} + r$ ，两式相减：

a_{n + 1} - x^{*} = p (a_{n} - x^{*}),

所以 ${a_{n} - x^{*}}$ 是公比为 $p$ 的等比数列。

a_{n + 1} = 3 a_{n} - 4

：不动点

x^{*} = 2

，

a_{n} = 2 + 3 \cdot 3^{n}

。拖

p

到

1

，不动点消失，数列变成等差数列。

重根与复根

两根相等时， $λ^{n}$ 只提供一个解，还缺一个——它是 $n λ^{n}$ 。两根是共轭复数时，公式里出现 $i$ ，但数列本身仍是整数，而且可能周期地来回摆动。

a_{n + 2} = a_{n + 1} - a_{n}

：特征根

\frac{1 \pm 3 i}{2}

的模是

1

，辐角是

6 0^{\circ}

，转六次回到原处——数列以

6

为周期。这正是下一站的主角。

什么时候不灵

Break it

反例实验室：去掉一个条件

结论：设 $a_{n} = A λ_{1}^{n} + B λ_{2}^{n}$ 就能配上任意初值

$a_{n + 2} = 5 a_{n + 1} - 6 a_{n}$ ，根 $2, 3$ 不等：两个初值、两个未知数，总能解出来。

练一练

练习 1基础

$a_{0} = 1, a_{n + 1} = 2 a_{n} + 3$ 。求 $a_{5}$ ，并写出通项。

练习 2基础

$a_{0} = 2, a_{1} = 1, a_{n + 2} = a_{n + 1} + 6 a_{n}$ 。求 $a_{6}$ 。

练习 3提高

$a_{0} = 1, a_{1} = 6, a_{n + 2} = 6 a_{n + 1} - 9 a_{n}$ 。求通项和 $a_{4}$ 。

练习 4挑战

由数字 $0, 1, 2$ 组成、长度为 $n$ 、没有两个 $0$ 相邻的字符串有 $f (n)$ 个。求 $f (5)$ ，并写出 $f (n)$ 满足的递推式和特征根。

这一招在做什么

跟着做一遍

例：a₀ = 1, a₁ = 4, a_{n+2} = 5a_{n+1} − 6aₙ

一阶的情形：减去不动点

重根与复根

什么时候不灵

反例实验室：去掉一个条件

练一练

错误博物馆 · 本站展品

初值是 a₁, a₂，却按 a₀, a₁ 去解系数