数学复健3-数学归纳法

小故事

一位工匠摆了一排骨牌，她先推倒第一块，第一块倒了。然后她发现任何一块骨牌倒下时，都会碰倒下一块骨牌。她没有逐块数到最后，也没有把每块骨牌都单独推一遍。

她只发现了两件事：

1. 第一块会倒；
2. 如果第 $n$ 块会倒，那么第 $n+1$ 块也会倒。

于是她得出结论，推倒第一个骨牌，整排骨牌都会倒下：

$$
1\text{ 倒}
\Longrightarrow
2\text{ 倒}
\Longrightarrow
3\text{ 倒}
\Longrightarrow
\cdots.
$$

注意，这个结论并不是由“我看见前几块倒了”得到的。

真正的逻辑是：起点成立 与 一步推进规则成立，那么所有有限步成立

数学归纳法面对的不是一排真的骨牌，而是一列自然数索引的命题：

$$
P(0),P(1),P(2),\ldots.
$$

其中 $P(n)$ 是“关于 $n$ 的命题”。

如果 $P(0)$ 成立，且：

$$
\forall n\in\mathbb N,\quad
P(n)\Longrightarrow P(n+1),
$$

那么：

$$
\forall n\in\mathbb N,\quad P(n).
$$

这是一种只使用有限证明步骤、却得到无限多个结论的方法。

历史插页

Pascal三角形

17 世纪，Pascal 在讨论算术三角形时系统使用了相邻层之间的关系：

从 $n$ 个不同对象中恰好选出 $k$ 个的选择数，记作二项式系数：

$$
\binom nk.
$$

这些选择数满足：

$$
\binom n k = \binom{n-1}{k-1} + \binom{n-1}{k}.
$$

这个公式把第 $n$ 层的数连接到第 $n-1$ 层的数。换句话说，较早的一层规定了较晚的一层。

这种“用较早项规定较晚项”的规则，下一章会正式命名为递推关系。在这里，我们只观察它为什么适合归纳证明：若上一层已经具有某个性质，公式便提供了一条把性质送到下一层的道路。

Dedekind 与 Peano：自然数需要什么规则

19 世纪末，Dedekind 和 Peano 分别推动了自然数系统的公理化描述。

核心思想可以概括为：

• 有一个起点；
• 每个数有一个后继；
• 不同数不会拥有同一个后继；
• 起点不是任何数的后继；
• 对满足起点和后继闭合条件的集合，可以得到全部自然数。

最后一条正是归纳原理的公理化影子。

自然数与命题谓词

后继

自然数的后继是“再增加一个”的操作，记作：

$$
S(n)=n+1.
$$

因此0的后继是1：

$$
S(0)=1,\qquad
S(1)=2,\qquad
S(2)=3.
$$

归纳法不是凭空选择 $n+1$。

它依赖自然数可以由起点和后继逐步生成：

$$
0,\ S(0),\ S(S(0)),\ldots.
$$

命题谓词

一个从自然数到命题的函数：

$$
P:\mathbb N\to{\text{命题}}
$$

叫作一个命题谓词。

例如：

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

这里 $P(n)$ 不是一个数，而是一个随 $n$ 变化的命题。

再例如：

$$
Q(n):\quad 2^n\geq n+1.
$$

它对每个自然数 $n$ 都给出一个真假陈述。

全称命题

说：

$$
\forall n\in\mathbb N,\quad P(n)
$$

表示：

对每一个自然数 $n$，命题 $P(n)$ 都成立。

这通常包含无限多个实例：

$$
P(0),P(1),P(2),P(3),\ldots.
$$

直接逐个验证不可能完成，因为验证过程本身若只做有限步，就只能覆盖有限多个 $n$。

归纳法解决的正是这个“无限对象如何由有限证明控制”的问题。

有界量词

如果量词只在某个由条件限制的范围内运行，就叫作有界量词。
例如：

$$
\forall j<k,\quad P(j)
$$

表示对所有满足 $j<k$ 的自然数 $j$，命题 $P(j)$ 都成立。
同样：

$$
\exists j\leq k,\quad P(j)
$$

表示至少存在一个满足 $j\leq k$ 的自然数 $j$，使 $P(j)$ 成立。
强归纳法会使用第一种有界全称量词。

数学归纳法

定理的完整形式

设 $P(n)$ 是一个关于自然数 $n$ 的命题。

如果满足：

1. 基础步骤：
   $$
   P(0)\text{ 成立}
   $$
2. 归纳步骤：
   $$
   \forall k\in\mathbb N,\quad
   P(k)\Longrightarrow P(k+1),
   $$

则：

$$
\forall n\in\mathbb N,\quad P(n)
$$

这里在归纳步骤中使用的 $k$ 叫作归纳变量。

在归纳步骤中，假设：

$$
P(k)
$$

成立，称为归纳假设；要证明的是：

$$
P(k+1).
$$

证明模板

写证明时可以按照下面的顺序：

1. 定义命题 $P(n)$；
2. 验证 $P(0)$；
3. 取任意 $k\in\mathbb N$，假设 $P(k)$；
4. 在这个假设下推出 $P(k+1)$；
5. 根据归纳法得到对所有 $n$ 成立。

例子：前 $n$ 个自然数的和

命题：

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

对所有 $n\in\mathbb N$ 成立。

证明：

定义：

$$
P(n):\quad \sum_{j=0}^{n}j = \frac{n(n+1)}2.
$$

基础步骤：

当 $n=0$ 时：

$$
\sum_{j=0}^{0}j=0,
$$

而：

$$
\frac{0(0+1)}2=0.
$$

所以 $P(0)$ 成立。

归纳步骤：

假设：

$$
\sum_{j=0}^{k}j = \frac{k(k+1)}2.
$$

那么：

$$
\sum_{j=0}^{k+1}j = \left(\sum_{j=0}^{k}j\right)+(k+1).
$$

使用归纳假设：

$$
\sum_{j=0}^{k+1}j = \frac{k(k+1)}2+(k+1).
$$

提取 $k+1$：

$$
\frac{k(k+1)}2+(k+1) = \frac{k(k+1)+2(k+1)}2.
$$

因此：

$$
\sum_{j=0}^{k+1}j = \frac{(k+1)(k+2)}2.
$$

这正是 $P(k+1)$。

所以：

$$
\forall n\in\mathbb N,\quad \sum_{j=0}^{n}j = \frac{n(n+1)}2.
$$

例子：等比和

命题：

$$
\sum_{j=0}^{n}r^j = \frac{r^{n+1}-1}{r-1}
$$

对 $r\neq1$ 和所有 $n\in\mathbb N$ 成立。

证明：

基础步骤：

$$
\sum_{j=0}^{0}r^j=1,
$$

右侧：

$$
\frac{r^{1}-1}{r-1}=1.
$$

归纳步骤：

假设：

$$
\sum_{j=0}^{k}r^j = \frac{r^{k+1}-1}{r-1}.
$$

则：

$$
\sum_{j=0}^{k+1}r^j = \frac{r^{k+1}-1}{r-1}+r^{k+1}.
$$

通分：

$$
\frac{r^{k+1}-1}{r-1} + \frac{r^{k+1}(r-1)}{r-1} = \frac{r^{k+2}-1}{r-1}.
$$

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

命题：

$$
2^n\geq n+1,\qquad \forall n\in\mathbb N.
$$

证明：

基础步骤：

$$
2^0=1=0+1.
$$

归纳假设：

$$
2^k\geq k+1.
$$

因为 $2>0$，两边乘以 $2$：

$$
2^{k+1}\geq2(k+1).
$$

而：

$$
2(k+1)\geq(k+1)+1
$$

因为 $k+1\geq0$。

所以：

$$
2^{k+1}\geq k+2.
$$

这就是 $P(k+1)$。

归纳法不是“多试几个例子”

反例：前几个值都对

考虑

命题：对所有自然数 $n$，数 $n^2+n+41$ 都是素数。

前几个值：

$$
41,\quad
43,\quad
47,\quad
53,\quad
61,\ldots
$$

看起来非常像素数。

但当 $n=40$ 时：

$$
40^2+40+41
=41^2,
$$

不是素数。

所以：

$$
\text{有限多个例子成立}
\not\Longrightarrow
\text{对所有自然数成立}.
$$

归纳步骤也可能是错的

有人试图证明“所有马都是同一种颜色”。

假设 $n$ 匹马都同色，试图把 $n+1$ 匹马分成两个重叠的 $n$ 匹集合。

当 $n\geq2$ 时，两个集合有共同的马，因此可以传递颜色。

但基础步骤从 $n=1$ 推到 $n=2$ 时，两个单匹集合没有共同元素。

错误发生在归纳步骤的边界。

这说明归纳证明必须逐一检查：

• 起点是否正确；
• 归纳变量范围是否正确；
• $P(k)$ 是否真的足以推出 $P(k+1)$；
• 有没有在某一步偷偷使用更强的假设。

归纳法可以从 $1$ 开始

如果命题从 $1$ 开始，可以使用：

$$
P(1),
$$

以及：

$$
\forall k\geq1,\quad
P(k)\Longrightarrow P(k+1).
$$

于是：

$$
\forall n\geq1,\quad P(n).
$$

起点不是永远必须是 $0$，关键是起点与推进范围要匹配。

强归纳法

为什么普通归纳有时不够

有些对象的第 $n$ 步不是只依赖第 $n-1$ 步，而是依赖所有更小的对象：

$$
P(0),P(1),\ldots,P(n-1).
$$

证明n时，不止使用n-1，而是使用许多小于n的命题

强归纳法的完整定义

设 $P(n)$ 是关于自然数的命题。

如果：

$$
\forall k\in\mathbb N,
\quad
\left[
\forall j<k,\ P(j)
\right]
\Longrightarrow
P(k),
$$

则：

$$
\forall n\in\mathbb N,\quad P(n)
$$

基础步骤被包含在 $k=0$ 的情形中，因为不存在 $j<0$。

例子：素因子分解的存在性

命题：

任何一个大于1的整数，都可以写成有限个素数相乘（素因子分解存在）。

整除的定义

若整数 $d,a$ 满足：

$$
\exists q\in\mathbb Z,\quad a=dq,
$$

就称 $d$ 整除 $a$，记作 $d\mid a$，也称 $d$ 是 $a$ 的一个因数。

素数的定义

一个大于 $1$ 的整数 $n$ ，若正因数只有 $1$ 和自身，就称为素数。

存在性证明

证明：

任取一个大于1的整数 $n$，假设介于1和 $n$ 的整数都可以分解为素数的乘积（这是一个强归纳假设）

如果 $n$ 是素数，$n=n$，结论成立

如果 $n$ 不是素数，则 $n$ 存在一对正因数不是1或者 $n$：

$$
1<a<n,
\qquad
1<b<n,
\qquad
n=ab.
$$

根据强归纳假设，$a$ 和 $b$ 都可以分解成素数乘积（在这里，$a,b$ 不是 $n-1$，但是我们为了证明 $n$ 的结论成立，用到了 $a,b$ 的结论，这就是强归纳法的普通归纳法的区别）。

于是 $n=ab$ 也可以分解成（素数乘积）·（素数乘积），所以 $n$ 还是可以被分解为素数的乘积。

因此所有 $n>1$ 都有这种分解。

Euclid 引理

若素数 $p$ 整除乘积 $ab$，则 $p$ 至少整除 $a$ 和 $b$ 中的一个：

$$
p\mid ab
\Longrightarrow
\left(p\mid a\right)\lor\left(p\mid b\right).
$$

例子：素因子分解的唯一性

命题：

$$
n=p_1p_2 \cdots p_s= q_1q_2 \cdots q_t
$$

其中 $p_i,q_j$ 都是素数，那么 $s=t$，并且适当重排下标后 $p_i=q_i$

证明：

归纳基：最小的 $n>1$ 是素数 $n=2$。

若 $2=p_1\cdots p_s=q_1\cdots q_t$，因为 2 是素数，只能 $s=t=1,p_1=q_1=2$，唯一性成立。

归纳假设：对所有整数 k 满足 $1<k<n$，k 的素因子分解在不计顺序意义下唯一。

现在考察 n 的两个素分解：

$n=p_1p_2\cdots p_s=q_1q_2\cdots q_t$
显然 $p_1\mid q_1q_2\cdots q_t$。
由 Euclid 引理的乘积推论：存在某个 j，使得 $p_1\mid q_j$。

但是 $q_j$ 是素数，它的正因子只有 1 和 $q_j$，而 $p_1>1$，所以只能：

$p_1=q_j$我们把等式两边同时约去这个素数 $p_1(=q_j)$：

$$
\frac{n}{p_1} =p_2p_3\cdots p_s =\prod_{\substack{i=1\i\neq j}}^t q_i
$$
记 $m=\dfrac{n}{p_1}$。因为 $p_1\ge 2$，所以 $m<n$，且 $m>1$。

根据强归纳假设，m 的素分解唯一（不计顺序）：
左边是 $p_2,\dots,p_s$；右边是去掉 $q_j$ 之后剩下的 q。
于是：

• 两边素数个数相等：$s-1 = t-1 \implies s=t$
• 剩下的素数适当重排后一一对应相等。

补上刚才相等的 $p_1=q_j$，就得到：原来两组素数，重排之后全部对应相等。

普通归纳与强归纳的关系

在标准自然数系统中，普通归纳法和强归纳法是等价的。

直觉上，可以把：

$$
\forall j<k,\ P(j)
$$

打包成一个新的命题：

$$
Q(k):\quad
\forall j\leq k,\ P(j).
$$

对 $Q(k)$ 使用普通归纳，就能恢复强归纳结论。

良序原理

良序原理：正整数的任意非空子集，都存在最小元

良序的定义

设 $X$ 是集合。对 $X$ 上的二元关系 $\leq$，写作 $a\leq b$，表示有序对 $(a,b)$ 属于这个关系。

如果 $\leq$ 满足：

1. 自反性：
   $$
   \forall a\in X,\quad a\leq a;
   $$
2. 反对称性：
   $$
   a\leq b\land b\leq a\Longrightarrow a=b;
   $$
3. 传递性：
   $$
   a\leq b\land b\leq c\Longrightarrow a\leq c;
   $$
4. 任意两个元素都可比较：
   $$
   \forall a,b\in X,\quad a\leq b\lor b\leq a;
   $$

那么 $\leq$ 叫作 $X$ 上的全序。

全序集合 $(X,\leq)$ 如果每个非空子集都有最小元素，就称为良序集。

这里，$m\in A$ 是 $A$ 的最小元素，是指：

$$
\forall a\in A,\quad m\leq a.
$$

自然数具有良序性：

$$
\varnothing\neq A\subseteq\mathbb N \Longrightarrow \exists m\in A,\quad \forall a\in A,\ m\leq a
$$

这叫作自然数的良序原理。

最小反例法

假设要证明：

$$
\forall n\in\mathbb N,\quad P(n).
$$

反设存在反例，令反例集合为：

$$
A={n\in\mathbb N\mid\neg P(n)}.
$$

若 $A\neq\varnothing$，良序原理给出最小反例 $m$。

如果能证明：

$$
\forall j<m,\quad P(j)
\Longrightarrow
P(m),
$$

就与 $m$ 是反例矛盾。

所以没有反例，命题成立。

这个证明策略叫作最小反例法。

例子：素因子分解的存在性

命题 $P(n)$：整数 $n>1$ 可以写成有限个素数的乘积。

证明：

反证。假设存在 $n>1$ 使得 $P(n)$ 不成立。令

$$
S={n\in\mathbb Z\mid n>1,;P(n)\text{ 为假}}
$$
由假设，$S\neq\emptyset$。
由良序原理，$S$ 含有最小元，记为 $m$（最小反例）。

现在分析 $m$：

• $m>1$，并且 m 不能写成素数乘积。

分两种情况：

1. 如果 $m$ 是素数：则 $m=m$ 本身就是单个素数的乘积，于是 $P(m)$ 成立。矛盾，因为 $m\in S$。
2. 如果 m 不是素数（合数）：
   根据素数定义，存在整数 $a,b$ 满足
   $1<a<m,\quad 1<b<m,\quad m=ab.$
   因为 $m$ 是 $S$ 的最小元，$a,b$ 都比 $m$ 小，所以 $a\notin S,;b\notin S$。
   也就是：$a,b$ 都可以写成素数乘积（反例子假设不成立）。
   于是 $m=ab$ 也是素数乘积，推出 $P(m)$ 成立。同样矛盾。

两种情况都矛盾。
因此 $S=\emptyset$，所有 $n>1$ 都满足 $P(n)$。

例子：素因子分解的唯一性

命题：若 $n>1$，并且

$n=p_1p_2\cdots p_s = q_1q_2\cdots q_t$
其中所有 $p_i,q_j$ 都是素数，则 $s=t$，并且重排下标后 $p_i=q_i$。

证明：
反证。假设存在整数 $n>1$，它有两种本质不同的素分解。
设

$$
S={n>1\mid n\text{ 有两种不计顺序互不相同的素分解}}.
$$
假设 $S\neq\emptyset$。由良序原理，$S$ 有最小元 $m$。
于是 $m$ 有两个分解：

$$
m = p_1p_2\cdots p_s = q_1q_2\cdots q_t \tag{1}
$$
且这两组素序列不能通过重排变成一样。

考察 $p_1$：$p_1\mid q_1q_2\cdots q_t$。
由 Euclid 引理的推广：素数整除乘积，则整除其中某一个因子。
于是存在某个下标 $j$，使得 $p_1\mid q_j$。
因为 $q_j$ 是素数，$p_1>1$，故 $p_1=q_j$。

在等式 (1) 两边约去 $p_1=q_j$：

$$
\frac{m}{p_1}=p_2\cdots p_s=\prod_{\substack{k=1\k\neq j}}^t q_k.
$$
记 $m’=\dfrac{m}{p_1}$，显然 $1<m’<m$。

现在看 $m’$ 的这两个分解：

• 如果这两个分解本身就已经是 “不计顺序相同” 的：
  那么补上 $p_1=q_j$，$m$ 的两个分解也一定重排后相同。
  这和 $m\in S$（$m$ 有不同分解）矛盾。
• 如果这两个分解互不相同，则 $m’\in S$。
  但 $m’<m$，这和 $m$ 是 $S$ 的最小元矛盾。

无论哪种情况都推出矛盾。
所以 $S=\emptyset$，不存在有两种不同素分解的正整数。唯一性成立。