数学归纳法¶
\[
\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\)自然也对任意正整数都成立。
类似地，我们也可以构造出对奇数成立、对偶数成立、对完全平方数成立等等的数学归纳法，方法与上述类似。