数学归纳法¶

\[ \renewcommand{\xfrac}{\displaystyle \frac} \renewcommand{\xsqrt}{\displaystyle \sqrt} \newcommand{\icr}{\!+\!\!+} \newcommand{\implies}{\Rightarrow} \renewcommand{\N}{\mathbb{N}} \] $$ \renewcommand{\xfrac}{\displaystyle \frac} \renewcommand{\xsqrt}{\displaystyle \sqrt} \newcommand{\icr}{\!+\!\!+} \renewcommand{\N}{\mathbb{N}} $$

数学归纳法(Method of Mathematical Induction)，简称归纳(induction)，是数学中一种特别常用的证明方法。

其基本思想是先证明某个数成立，再证明“当某个数成立时，其后继数也成立”。深入思想是证明后继数的存在性。

它是从有限到无限的几乎唯一的方法，因此在数学中有重要作用。

Peano公理与数学归纳原理¶

Peano公理¶

皮亚诺公理(The Peano Axioms)是由皮亚诺(Peano)给出的五个关于自然数的基本性质。在学习数学归纳法之前，我们先简单了解一下Peano公理。

这里我们记$\mathbb{N}$为自然数集（我们约定自然数从0开始），再定义符号$n \icr$，表示$n$的后继，即下一位自然数，并称该运算为“自增”运算。例如$2 \icr = 3$，$9 \icr = 10$，等等。

公理1：$0$是自然数，即$0 \in \mathbb{N}.$
公理2：如果$n$是自然数，那么$n\icr$也是自然数，即$n\in\N \implies n\icr\in\N.$
公理3：$0$不是任何数的后继数，即$\forall n\in\N: n\icr\ne0.$
公理4：不同的自然数有不同的后继数，即$\forall m,n \in \N:(m\ne n \implies m\icr \ne n \icr).$
公理5：数学归纳原理。

前四条公理实际上定义了一个基本的自然数集，它保证了自然数的起点、后继、不循环至0、不陷入死循环（关于这些，可以参阅《陶哲轩实分析》）。但是，前四条公理对自然数是不够的，例如：

Example

定义数集$\N={0,0.5,1,1.5,2,2.5,\dots}$，它由所有的正常的自然数和“自然数$+0.5$”构成。

定义：$n\icr = n+1, n.5\icr = n.5 + 1.$

可以验证，这样定义的数集也是满足以上四个公理的。为了避免有些数“见缝插针”，插入到自然数的缝隙内，我们需要再补充一条公理，让数 $0$ 以及自增运算 $+\!+$ 能够“遍历”所有的自然数。

数学归纳原理¶

公理（数学归纳原理）

若集合$S$满足：

$0\in S,$
如果$n \in S$，那么一定有$n \icr \in S$，也就是$n \in S \implies n \icr \in S;$

则$S$是自然数集，即$S = \N.$

这个公理保证了任何一个自然数都可以通过 0 做有限次自增运算得到，消除了自然数的 bug，完整地定义了自然数。它也成为了数学归纳法的基础。

数学归纳法¶

以数学归纳原理为基础，我们可以引出最基本的归纳法：

从零开始的数学归纳¶

要证明某个性质$p(n)$对所有的自然数成立，只需要先证明$p(0) \equiv \mathbf{T}$，然后假设 $p(n)$ 成立，以此为条件证明$p(n\icr)$也成立。

这里令集合$S = \{n|p(n)\}$，立即可由数学归纳原理推得证明方法的正确性。

Example

定义从自然数对到自然数的一个函数$f(m,n): {\N}^2 \to \N$如下。

对任意的自然数$m,n$：

$f(0,n) = n,$
$f(m\icr,n) = f(m,n) \icr.$

用数学归纳法证明：对任意的自然数$m,n$有$f(m,n) = f(n,m)$。

Proof

证明可以分三步。

第一步我们先证明：$\forall n\in \N:f(n,0) = n$。由函数$f$的定义1，$f(0,0)=0$；再假设$f(n,0)=n$，则$f(n\icr,0) = f(n,0)\icr = n\icr$；于是由数学归纳原理，$f(n,0)=n$对任意的正整数$n$都成立。

第二步我们证明：$f(m,n\icr) = f(m,n)\icr$。我们对第一个变量$m$归纳。首先当$m = 0$时，由$f$的定义，有$f(0,m)=m$和$f(0,m\icr)=m\icr$；然后再假设$f(m,n\icr)=f(m,n)\icr$，我们需要证明$f(m\icr,n\icr) = f(m\icr,n)\icr$。由$f$的定义2，左边$f(m\icr,n\icr) = f(m,n\icr)\icr$，再由归纳假设，$f(m,n\icr)\icr = (f(m,n)\icr)\icr$，再由$f$的定义2，有$f(m,n)\icr = f(m\icr,n)$，于是$(f(m,n)\icr)\icr = f(m\icr,n)\icr$，等于右边。因此由数学归纳原理，$f(m,n\icr)=f(m,n)\icr$。

第三步我们证明：$f(m,n) = f(n,m)$。对$m$归纳。当$m = 0$时，由$f$的定义1和证明的第一步，我们有$f(0,n) = n = f(n,0)$。然后我们假设$f(m,n)=f(n,m)$，则对$m\icr$，由$f$的定义2，有$f(m\icr,n) = f (m,n)\icr$；再由归纳假设，有$f(m,n)\icr=f(n,m)\icr$；然后由证明的第二步，有$f(n,m)\icr = f(n,m\icr)$；于是由三个等式传递，得到$f(m\icr,n)=f(n,m\icr)$。由数学归纳原理，对任意自然数$m,n$都有$f(m,n)=f(m,n)$。

Tip

这里的函数$f$实际上就是自然数的加法(Addition)运算，或者说，上面的两个定义就是自然数加法的定义，也就是$m + n = f(m,n)$。从这个定义来看，加法交换律并不是显然的，而是需要严谨证明的。在这个证明过程我们也发现了数学归纳法的强大之处。

定义了加法之后，很容易证明$n \icr = n + 1$。因此，下面我们使用大家更熟悉的$n + 1$来代替符号$n \icr$，数学归纳法也就是证明$p(0)$以及$p(n) \Rightarrow p(n+1)$。

类似地，读者也可以尝试证明下面一题：

Example

定义自然数对到自然数的二元函数$g$如下：

$g(0,n) = 0,$
$g(m+1,n) = g(m,n)+n.$

证明：$g(m,n) = g(n,m)$。函数$g$称为自然数的乘法(Multiplication)。

从其他数开始¶

数学归纳法可以从别的数开始吗？当然是可以的。

如何证明数学归纳法可以从1开始呢？假设有某个性质$q(n)$对正整数$\mathbb{Z}^+$都成立，并且对任意的$n \in \mathbb{Z}^+$都有$q(n) \implies q(n + 1)$。

这里的$q(n)$是从$n=1$开始的，不过并不麻烦，我们只要做一个平移，让$p(n) = q(n+1)$，这样$p(0)=q(1)$成立，且$p(n) \implies p(n + 1)$，所以$p$对任意自然数$n$都成立。而性质$q$比性质$p$“落后”一位，所以性质$q$自然也对任意正整数都成立。

类似地，我们也可以构造出对奇数成立、对偶数成立、对完全平方数成立等等的数学归纳法，方法与上述类似。