递推方法

一句话

设 $a_{n}$ 是规模为 $n$ 时的答案。别去硬数 $a_{n}$ ，而是问：最后一个元素怎么样？ 每种情况拿掉它之后，剩下的往往正是规模 $n - 1$ 、 $n - 2$ 的同一个问题。

a_{n} = (情况一) + (情况二) = a_{n - 1} + a_{n - 2}

于是四步走：① 用 $a_{n}$ 表示所求；② 亲手算出初值 $a_{1}, a_{2}, \dots$ ；③ 建立递推关系；④ 由递推求出 $a_{n}$ （迭代、特征方程或直接算到需要的项）。

先猜后证

${1, 2, \dots, 10}$ 中，不含两个相邻整数的子集（包括空集）有多少个？

89

144

233

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

例：不含相邻两数的子集

第 1 / 5 步

设未知量，数初值
设 $a_{n}$ 为 ${1, \dots, n}$ 中不含相邻两数的子集个数。 $a_{1} = 2$ ： $\emptyset, {1}$ 。

$a_{1} = 2$
第二个初值
看最后一个元素
递推关系
求出来

第 1 站 · 有限集的计数：错排（卷一）

把 $1, 2, \dots, n$ 重新排列，使每个数都不在自己原来的位置上，叫错排。还是看最后一个数 $n$ 去了哪里、谁来了位置 $n$ 。

例：错排数 Dₙ 的递推

第 1 / 5 步

小的情形
$D_{1} = 0$ ， $D_{2} = 1$ （ $21$ ）， $D_{3} = 2$ （ $231, 312$ ）。

$D_{1} = 0, D_{2} = 1, D_{3} = 2$
按 n 去了哪里分类
互换的一类
不互换的一类
递推

第 2 站 · 线性递推与特征方程（卷五）

递推式建好以后，若它是常系数线性的，特征方程直接给出通项。

例：用 0, 1, 2 组成长为 n 的串，不出现两个相邻的 0，有多少个？

第 1 / 4 步

看最后一位
设个数为 $b_{n}$ 。最后一位是 $1$ 或 $2$ ：前面任意合格， $2 b_{n - 1}$ ；最后一位是 $0$ ：倒数第二位只能是 $1$ 或 $2$ ， $2 b_{n - 2}$ 。

$b_{n} = 2 b_{n - 1} + 2 b_{n - 2}$
初值
特征方程
定系数

第 3 站 · 函数迭代（卷二）

$f^{(n)} (x) = f (f^{(n - 1)} (x))$ 本身就是递推。关键是找一个量，让这条递推变简单。

一题多解

$f (x) = \frac{x}{1 + x}$ （ $x > 0$ ），求 $f^{(n)} (x)$ 。

先猜后证

$f^{(2)} (x) = \frac{x / ( 1 + x )}{1 + x / ( 1 + x )} = \frac{x}{1 + 2 x}$ ， $f^{(3)} (x) = \frac{x}{1 + 3 x}$ 。猜 $f^{(n)} (x) = \frac{x}{1 + n x}$ ；若对 $n$ 成立，则 $f^{(n + 1)} (x) = \frac{x / ( 1 + n x )}{1 + x / ( 1 + n x )} = \frac{x}{1 + ( n + 1 ) x}$ 。

代价要算几项才能看出规律，再补一次归纳。

取倒数，化成等差递推

记 $u_{n} = \frac{1}{f ^{(n)} ( x )}$ 。由 $\frac{1}{f ( y )} = \frac{1}{y} + 1$ 得 $u_{n} = u_{n - 1} + 1$ ， $u_{0} = \frac{1}{x}$ 。所以 $u_{n} = \frac{1}{x} + n$ ， $f^{(n)} (x) = \frac{x}{1 + n x}$ 。

代价一眼看穿，不必猜。

第 4 站 · 函数方程的递归法（卷二）

定义在正整数上的函数方程，令其中一个变量取 $1$ ，就得到关于 $f (n)$ 的递推。

例：f: N⁺ → R，f(1) = 1，f(m + n) = f(m) + f(n) + mn，求 f(n)

第 1 / 3 步

让一个变量取 1
令 $m = 1$ ： $f (n + 1) = f (n) + f (1) + n = f (n) + n + 1$ 。

$f (n + 1) - f (n) = n + 1$
累加
验证

练一练

练习 1基础

${1, 2, \dots, 8}$ 中不含两个相邻整数的子集（包括空集）有多少个？

练习 2基础

$5$ 个人各写一张贺卡，放在一起后每人随机取一张，没有人拿到自己写的贺卡的取法有多少种？

练习 3提高

用 $0, 1, 2$ 组成长为 $5$ 的串（首位可以是 $0$ ），其中不出现两个相邻的 $0$ ，有多少个？

练习 4挑战

平面上 $6$ 个圆，每两个圆都交于两点，且任意三个圆不过同一点。它们把平面分成多少块？

一句话

例：不含相邻两数的子集

第 1 站 · 有限集的计数：错排（卷一）

例：错排数 Dₙ 的递推

第 2 站 · 线性递推与特征方程（卷五）

例：用 0, 1, 2 组成长为 n 的串，不出现两个相邻的 0，有多少个？

第 3 站 · 函数迭代（卷二）

先猜后证

取倒数，化成等差递推

第 4 站 · 函数方程的递归法（卷二）

例：f: N⁺ → R，f(1) = 1，f(m + n) = f(m) + f(n) + mn，求 f(n)

练一练

错误博物馆 · 本站展品

递推式对了，初值错了

分类时漏了一类

这条线路经过的站