递推与归纳

一句话

大问题里藏着小一号的自己。

想知道 $n$ 的答案，先别硬数。盯住最后一步，把它拿掉，剩下的往往就是 $n - 1$ （或 $n - 2$ ）时的同一个问题。于是答案之间有了关系——递推式。再加上最开头的一两个值，后面的每一项都能一步步算出来；要证明规律永远成立，就用数学归纳法：起点成立，并且每一项都能推出下一项。

先猜后证

用 1×2 的骨牌铺满 2×6 的长条，一共有多少种铺法？（先凭感觉猜一个数。）

种

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

例：2×n 长条的铺法数

第 1 / 6 步

最小的情形
2×1 只能竖放一块， $f (1) = 1$ 。

$f (1) = 1$
再大一点
盯住最右边
拿掉收尾的牌
递推式
一路算下去

找递推的口诀：看最后一步有几种可能，每种可能把问题缩小成什么。

第 1 站 · 计数（卷七）

平面上画 $n$ 条直线，任何两条都相交，任何三条不过同一点。它们把平面分成多少块？

先猜后证

$4$ 条这样的直线把平面分成 $11$ 块。再添第 $5$ 条，会分成多少块？

块

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

例：n 条直线分平面

第 1 / 5 步

起点
没有直线时，平面是完整的 $1$ 块。

$L (0) = 1$
添一条线
盯住新添的那条
把递推“摊开”
用归纳法验一遍

第 2 站 · 操作与游戏（卷七）

汉诺塔：三根柱子， $n$ 个大小不同的圆盘从大到小叠在第一根上。每次只能搬一个盘，大盘不能压在小盘上。把整摞搬到第三根，最少要几步？

例：汉诺塔的最少步数

第 1 / 5 步

起点
只有 $1$ 个盘，搬 $1$ 步。

$T (1) = 1$
盯住最大的盘
三段
算几项，猜公式
归纳法证明

为什么不能更少？最大的盘至少要搬一次；它动身之前，其余 $n - 1$ 个盘必须整摞让到另一根柱子上，这至少 $T (n - 1)$ 步；它落定之后，那一摞还要再搬过来，又至少 $T (n - 1)$ 步。

第 3 站 · 勾股方程（卷六）

递推不只用来数数，还能造出无穷多个解：有了一个解，想办法从它造出下一个。

$3^{2} + 4^{2} = 5^{2}$ 里，斜边只比长直角边多 $1$ 。这样的勾股数还有吗？有多少？

例：斜边比直角边多 1 的勾股数

第 1 / 5 步

把条件写简单
设三边是 $a, b, b + 1$ 。展开 $(b + 1)^{2}$ ，两边消去 $b^{2}$ 。

$a^{2} + b^{2} = (b + 1)^{2} ⟺ a^{2} = 2 b + 1$
从一个解造下一个
新的 b
让它转起来
归纳：永远停不下来

反过来用也行：如果能证明“有一个正整数解，就一定有一个更小的正整数解”，那就永远小下去——而正整数不可能无限变小，所以根本没有解。这叫无穷递降法，是递推倒着走。

练一练

练习 1基础

上楼梯，每步可以跨 $1$ 级或 $2$ 级。上一段 $8$ 级的楼梯，一共有多少种不同的走法？

练习 2提高

还是上楼梯，但现在每步可以跨 $1$ 级、 $2$ 级或 $3$ 级。上 $7$ 级楼梯有多少种走法？

练习 3挑战

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

错误博物馆 · 本站展品

离站之前，看看别人在这里踩过的坑。去博物馆看全部展品 →

展品

验了很多项，就当证明了

n^{2} + n + 41

在

n = 0, 1, 2, \dots, 10

时都是素数（

41, 43, 47, 53, \dots, 151

），所以它对一切自然数

n

都是素数。

错在哪里？先想一想，再打开

病因　验算再多也只是有限项。事实上它一直到 $n = 39$ 都是素数，可是 $n = 40$ 时 $4 0^{2} + 40 + 41 = 1681 = 4 1^{2}$ ，不是素数。没有“从 $n$ 推到 $n + 1$ ”这一步，规律随时可能断。

归纳法要两条腿：① 起点成立；② 假设第

k

个成立，推出第

k + 1

个成立。小数据只用来猜，递推关系才用来证。

「验算是猜，递推才是证」

展品

递推式对了，起点错了

2×n 长条的铺法满足

f (n) = f (n - 1) + f (n - 2)

，这是斐波那契数列

1, 1, 2, 3, 5, 8

，所以 2×6 的长条有

8

种铺法。

错在哪里？先想一想，再打开

病因　递推式只说“后一项怎样由前两项得到”，不告诉你从哪里开始。这里 $f (1) = 1$ ， $f (2) = 2$ （两块都竖，或两块都横），不是 $1, 1$ 。

先亲手数出起点：

f (1) = 1, f (2) = 2

。再递推：

3, 5, 8, 13

。所以

f (6) = 13

。用到前两项的递推，就要两个起点。

「递推用到前几项，就要数清几个起点」

一句话

第 1 站 · 计数（卷七）

第 2 站 · 操作与游戏（卷七）

第 3 站 · 勾股方程（卷六）

练一练

错误博物馆 · 本站展品

这条线路经过的站