为什么需要归纳法
MATH1025 中很多命题不是关于某一个数，而是关于所有正整数。例如
13+23+⋯+n3=(2n(n+1))2
在 n=1,2,3,4 时都成立，但有限次检查并不能证明无限多个情形。数学归纳法
把一个真实的起点和一个可重复的下一步合成完整证明。
核心直觉是：如果第一个命题是真的，而且每个真命题都推出下一个，那么这条链
不会中断。
以整数为索引的命题
定义
索引命题
索引命题是一族命题 P(n)，每个允许的整数 n 都对应一个命题。P(n) 可以
对某些 n 成立，对另一些 n 不成立。
写归纳证明之前，必须先明确 P(n) 是什么。否则归纳假设会变成一句没有具体
内容的话。
定理
数学归纳法原理
设 P(n) 是每个 n∈Z+ 对应的命题。若：
P(1) 成立；- 对任意整数 k≥1，若
P(k) 成立，则 P(k+1) 成立；
则 P(n) 对所有 n∈Z+ 成立。
第二项是条件命题。证明时可以使用 P(k)，但目标是推出 P(k+1)。
标准证明格式
一个完整的归纳证明通常包含四部分：
- 定义
P(n)；
- 验证基础情形；
- 假设某个任意的
P(k) 成立，并推出 P(k+1)；
- 引用归纳法原理结束证明。
这些步骤让无限命题的证明结构清楚可查。
例题
立方和公式
证明对所有 n∈Z+，
13+23+⋯+n3=4n2(n+1)2.令 P(n) 为上述等式。当 n=1 时，左边为 1，右边为
412(1+1)2=1,所以 P(1) 成立。
假设 P(k) 对某个 k≥1 成立，即
13+23+⋯+k3=4k2(k+1)2.则
13+⋯+k3+(k+1)3=4k2(k+1)2+(k+1)3=(k+1)2(4k2+k+1)=(k+1)24(k+2)2.这正是 P(k+1)。因此公式对所有正整数成立。
关键不是单纯化简，而是用归纳假设替换前 k 项的和。
整除命题
定义
整除
若 m,n∈Z，且存在 q∈Z 使 m=nq，则称 m 被 n 整除，
记作 n∣m。
例题
一个整除证明
证明对所有 n∈Z+，3∣(n3−n)。
令 P(n) 为 3∣(n3−n)。当 n=1 时，
13−1=0=3⋅0，所以基础情形成立。
假设 P(k) 成立，即 k3−k=3q，其中 q∈Z。则
(k+1)3−(k+1)=k3+3k2+3k+1−k−1=(k3−k)+3k2+3k=3q+3k2+3k=3(q+k2+k).因为 q+k2+k 是整数，所以 P(k+1) 成立。
常见错误
常见错误
归纳步骤必须接上基础情形
如果一个归纳论证在 n=1 到 n=2 的过渡已经失效，那么即使之后看似合理，
也不能证明原命题。
常见错误
有限例子不是证明
验证 P(1), P(2), P(3) 可以帮助发现规律，但不能代替处理任意 k 的
归纳步骤。
变形
若命题从 n0 开始，基础情形就是 P(n0)，归纳步骤要从任意
k≥n0 推到 k+1。若命题按奇偶分开，也可以用 P(k) 推 P(k+2)，
但必须给出对应的起点。
定理
强归纳法
若 P(1) 成立，且对每个 k≥1，从
P(1),P(2),…,P(k) 全部成立可推出 P(k+1)，则 P(n) 对所有
n∈Z+ 成立。
强归纳法适合下一步依赖多个较早情形的证明。
快速检查
快速检查
在归纳步骤中，P(k) 和 P(k+1) 的角色有什么不同？
快速检查
为什么只检查 n=1,2,3 不能证明所有正整数情形？
快速检查
若命题声称对所有 n≥5 成立，基础情形应该是哪一个？
练习
- 用归纳法证明
1+2+\cdots+n=n(n+1)/2。
- 证明对所有 n∈Z+，4∣(5n−1)。
- 证明对所有整数 n≥5，n2<2n。
- 说明“重叠子集”的错误归纳证明为什么在第一个非平凡步骤失效。
引导解答
- 在归纳步骤中，把 k+1 加到
1+\cdots+k=k(k+1)/2 两边并化简。
- 若 5k−1=4q，则 5k+1−1=5(4q+1)−1=4(5q+1)。
- 从 n=5 开始。若 k2<2k 且 k≥5，利用 2k+1<2k 得到
(k+1)2<2k+1。
- 从一个对象到两个对象时，两个一元素子集没有重叠，因此性质不能传递过去。