数学归纳法 I：公式、整除与不等式

很多数学命题不是只问一个数，而是问一整串数。比如“对所有正整数 $n$ ， $1+2+\cdots+n=\frac{n(n+1)}{2}$ ”，这里真正要证明的不是一个等式，而是一族命题：

P(1),P(2),P(3),\ldots

数学归纳法处理的正是这种情况。它不逐个证明无穷多个命题，而是证明一个起点成立，并证明只要某一步成立，下一步也成立。这样结论就会沿着自然数的顺序一格一格传下去。

普通归纳法适合证明形如“对所有 $n\ge n_0$ ，命题 $P(n)$ 成立”的结论。本章先讨论最常见的一步归纳：从 $P(k)$ 推出 $P(k+1)$ 。强归纳和递归定义会在下一章继续展开。

普通数学归纳法三段式结构图，展示归纳基础、归纳假设和归纳步骤，并用自然数轴说明从 n0 到 k 和 k+1 的成立传递。

普通归纳法的三段式结构：先证明起点成立，再假设某一步成立，最后推出下一步成立。

归纳法在证明什么

归纳法证明的对象通常写成 $P(n)$ 。这里的 $P$ 不是一个数，而是“关于 $n$ 的命题”。当 $n$ 取不同值时，就得到不同的具体断言。

例如命题

P(n):1+2+\cdots+n=\frac{n(n+1)}{2}

包含下面这些具体等式：

P(1):1=\frac{1\cdot2}{2}

P(2):1+2=\frac{2\cdot3}{2}

P(3):1+2+3=\frac{3\cdot4}{2}

我们可以检查前几个值，但检查再多，也只能说明“这些值成立”。归纳法要证明的是从某个起点开始，所有后续值都成立。

多米诺直觉

多米诺模型把归纳法的两个条件画得很清楚。第一块要先倒下，这对应归纳基础；每块倒下后能推倒下一块，这对应归纳步骤。少了其中任意一个条件，都不能推出整列全倒。

一排多米诺骨牌从 n₀ 开始依次排列，第一块已倒下，展示基础步骤与连锁规则如何覆盖所有自然数。

多米诺直觉：先倒第一块，每块再推倒后一块，于是整列都会倒下。

台阶直觉

台阶模型强调另一个要点：归纳法不是直接跳到任意遥远的第 $n$ 阶，而是证明从第一阶开始，每次都能向上走一阶。

数学归纳法台阶模型示意图：从基础 n0 出发，已到达第 k 阶，并证明可到第 k+1 阶，从而覆盖所有后续台阶。

归纳法不是一次跳到终点，而是证明基础成立且每一步都能走到下一步。

归纳法中的 $k$ 不是一个固定的特殊数字。写“假设 $P(k)$ 成立”时，意思是：任选一个已经不小于起点的整数 $k$ ，如果第 $k$ 个命题成立，那么要推出第 $k+1$ 个命题也成立。

标准证明模板

要用普通归纳法证明“对所有整数 $n\ge n_0$ ， $P(n)$ 成立”，通常写成三段。

先证明归纳基础。把 $n=n_0$ 代入 $P(n)$ ，直接检查这个起点命题成立。起点不一定总是 $1$ ，它必须和题目中的范围一致。

可以把模板压缩成下面的逻辑骨架：

P(n_0)

\forall k\ge n_0,\; P(k)\Rightarrow P(k+1)

于是

\forall n\ge n_0,\; P(n)

写归纳假设时要说清楚什么

归纳假设不是“假设结论成立”。它只假设当前这一格 $P(k)$ 成立，然后借它推出下一格 $P(k+1)$ 。如果题目要证明的是一个公式，归纳假设就是把公式中的 $n$ 全部换成 $k$ ；目标则是把 $n$ 全部换成 $k+1$ 。

例如对命题

P(n):1+3+5+\cdots+(2n-1)=n^2

归纳假设应是

1+3+5+\cdots+(2k-1)=k^2

归纳步骤的目标应是

1+3+5+\cdots+(2k-1)+(2k+1)=(k+1)^2

危险写法是：“假设 $1+3+\cdots+(2k+1)=(k+1)^2$ 成立，然后证明它成立。”这已经把下一步目标放进了假设，证明就变成了循环。

求和公式的归纳证明

求和公式最适合训练归纳法，因为 $P(k+1)$ 的左边通常可以拆成“ $P(k)$ 的左边 + 新增最后一项”。

数学归纳法求和公式拆项图，左侧用方块阶梯表示已知部分并高亮新增最后一项，右侧展示整理到目标式的过程。

从 $P(k)$ 推到 $P(k+1)$ 时，将 $1+2+\cdots+k$ 与新增最后一项 $k+1$ 分开，再整理为目标式。

例题：前 n 个正整数之和

证明对所有正整数 $n$ ，

1+2+\cdots+n=\frac{n(n+1)}{2}

证明归纳基础。取 $n=1$ ，左边是 $1$ ，右边是 $\frac{1\cdot2}{2}=1$ ，所以成立。

交互验证能帮助你看见公式的规律，但它本身不是证明。证明需要说明任意一步 $k$ 到 $k+1$ 都能通过，而不是只列出若干个数值样本。

例题：前 n 个奇数之和

证明对所有正整数 $n$ ，

1+3+5+\cdots+(2n-1)=n^2

当 $n=1$ 时，左边为 $1$ ，右边为 $1^2=1$ ，所以归纳基础成立。

求和题的固定动作

求和公式的归纳步骤常常按这个顺序写：

写出 $P(k+1)$ 左边。
把它拆成 $P(k)$ 左边加新增项。
用归纳假设替换旧和式。
做代数整理，得到 $P(k+1)$ 右边。

这个动作看似机械，但它能防止最常见的错误：把目标式直接代入，而没有说明为什么可以替换。

整除命题的归纳证明

整除命题的语言是“某个表达式是某个数的倍数”。如果要证明 $a\mid b_n$ ，归纳假设通常写成

b_k=aq

其中 $q$ 是某个整数。归纳步骤的目标是把 $b_{k+1}$ 变形成“旧的倍数 + 新的倍数”。

整除命题归纳转化图，展示用归纳假设将 4^(k+1)-1 写成旧的 3 的倍数加新的 3 的倍数

证明 $3\mid(4^n-1)$ 时，将 $4^{k+1}-1$ 变形为 $4(4^k-1)+3$ ，从而得到旧的的倍数与新的的倍数之和。

例题：证明 3 整除 4^n - 1

证明对所有正整数 $n$ ，

3\mid(4^n-1)

先看 $n=1$ 。有 $4^1-1=3$ ，显然 $3\mid3$ ，所以归纳基础成立。

例题：证明 n³ - n 被 3 整除

证明对所有正整数 $n$ ，

3\mid(n^3-n)

当 $n=1$ 时， $1^3-1=0$ ，而 $3\mid0$ ，归纳基础成立。

整除题的关键不是“算出结果”，而是把目标表达式组织成某个整数倍。归纳假设给你一个已经确定的倍数，剩下的工作是把下一项凑到这个倍数旁边。

不等式命题的归纳证明

不等式归纳比公式归纳多一个细节：每一步放缩都要保持方向正确。你不能只把 $P(k)$ 写下来，还要说明从 $P(k)$ 到 $P(k+1)$ 的每个不等号为什么成立。

坐标轴比较 2^n 与 n+1 在 n=1 到 n=7 的增长，并展示不等式归纳放缩步骤

不等式归纳中的放缩：由已知下界推出下一步目标，注意不等号方向保持，且最后一步需单独说明。

例题：指数增长超过线性增长

证明对所有正整数 $n$ ，

2^n\ge n+1

当 $n=1$ 时， $2^1=2$ ， $1+1=2$ ，所以成立。

例题：调和型不等式

证明对所有整数 $n\ge1$ ，

1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{2^n}\ge1+\frac{n}{2}

这道题的左边不是加到 $n$ ，而是加到 $2^n$ 。归纳步骤从 $n=k$ 到 $n=k+1$ 时，新增的是

\frac{1}{2^k+1}+\frac{1}{2^k+2}+\cdots+\frac{1}{2^{k+1}}

共有 $2^k$ 项，每一项都至少是 $\frac{1}{2^{k+1}}$ ，所以新增部分至少为

2^k\cdot\frac{1}{2^{k+1}}=\frac{1}{2}

当 $n=1$ 时，左边为 $1+\frac12$ ，右边为，归纳基础成立。

不等式归纳常常卡在“目标比我手里的式子强还是弱”。如果你要证明下界，就需要让左边变得更小但仍不低于目标；如果你要证明上界，就需要让左边变得更大但仍不超过目标。每一次放缩都要朝目标方向走。

为什么不能假设结论本身

归纳法最容易写错的地方，是把“允许假设 $P(k)$ ”误读成“允许假设要证明的结论”。这两者差别很大。

允许假设的是：

P(k)

要证明的是：

P(k+1)

二者只差一步，但逻辑地位完全不同。归纳假设是已经站住的第 $k$ 阶； $P(k+1)$ 是你要迈上的下一阶。

一个错误证明长什么样

命题：对所有正整数 $n$ ，

1+2+\cdots+n=\frac{n(n+1)}{2}

错误证明可能这样写：

设 $k\ge1$ 。假设 $1+2+\cdots+k+(k+1)=\frac{(k+1)(k+2)}{2}$ 成立，所以成立。于是原命题成立。

这段话的问题是，它从一开始就假设了 $P(k+1)$ ，也就是归纳步骤的目标。真正的归纳假设只能停在 $k$ ：

1+2+\cdots+k=\frac{k(k+1)}{2}

然后必须通过加上 $k+1$ 和代数整理推出 $P(k+1)$ 。

归纳证明检查表

写完归纳证明后，可以逐项检查：

命题 $P(n)$ 是否说清楚了？
起点 $n_0$ 是否和题目范围一致？
归纳基础是否真的代入了 $n_0$ ？
归纳假设是否只写了 $P(k)$ ？

一个合格的归纳步骤应该能回答这句话：如果第 $k$ 个命题已经成立，我具体用它的哪一部分推出了第 $k+1$ 个命题？

综合练习

练习时先不要急着写完整证明。先写出 $P(n)$ 、归纳基础、归纳假设和 $P(k+1)$ 的目标式，再决定需要哪一种变形。

练习：平方和公式

证明对所有正整数 $n$ ，

1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}

先写归纳假设：

1^2+2^2+\cdots+k^2=\frac{k(k+1)(2k+1)}{6}

练习：一个整除命题

证明对所有正整数 $n$ ，

5\mid(6^n-1)

当 $n=1$ 时， $6^1-1=5$ ，所以归纳基础成立。

设 $k\ge1$ ，假设 $5\mid(6^k-1)$ 。于是存在整数，使得

练习：一个不等式命题

证明对所有整数 $n\ge4$ ，

2^n\ge n^2

当 $n=4$ 时， $2^4=16$ ， $4^2=16$ ，归纳基础成立。

设 $k\ge4$ ，假设

本章小结

数学归纳法把无穷多个命题排成一条链。归纳基础保证链条有起点，归纳步骤保证链条不会中断，归纳假设则是从当前一环走到下一环时允许使用的条件。

求和公式的常见动作是“拆出新增最后一项”；整除命题的常见动作是“写成旧倍数加新倍数”；不等式命题的常见动作是“沿着目标方向放缩，并说明每个不等号”。只要始终分清 $P(k)$ 和 $P(k+1)$ ，归纳证明就会有清楚的骨架。

1 + \frac{1}{2}

1+\frac12

离散数学与证明 I：逻辑、集合、归纳、计数与图论入门｜第 9 章：数学归纳法 I：公式、整除与不等式 | 自在学