MathLabs
公理已证明

数学归纳法原理

命题陈述

设 P(n)P(n) 是依赖自然数 n≥n0n \ge n_0 的命题。若（基础步骤）P(n0)P(n_0) 为真，且（归纳步骤）对任意 k≥n0k \ge n_0，P(k)P(k) 为真可推出 P(k+1)P(k+1) 为真，则 P(n)P(n) 对所有整数 n≥n0n \ge n_0 均为真。

为什么成立?

归纳法就像攀登一架无限的梯子：如果你能登上第一级，并且从任何一级总能登上下一级，那么无论多高，你都能登上每一级。你永远不需要逐一检查无穷多级台阶——只需检查第一步和『下一步』机制，就足以一次性覆盖全部。

证明思路

该原理由自然数的良序性得出：{n0,n0+1,… }\{n_0, n_0+1, \dots\} 的任何非空子集都有最小元。反证：设集合 SS 是所有 n≥n0n \ge n_0 中使 P(n)P(n) 为假的那些整数所构成的集合，并设其非空，设 mm 为其最小元。由于 P(n0)P(n_0) 为真，m≠n0m \ne n_0，故 m−1≥n0m - 1 \ge n_0 且 m−1∉Sm-1 \notin S（因 mm 最小），即 P(m−1)P(m-1) 为真。由归纳步骤，P(m)P(m) 必为真，与 m∈Sm \in S 矛盾。故 SS 为空集，P(n)P(n) 对所有 n≥n0n \ge n_0 成立。（等价地，归纳法与 N\mathbb{N} 的良序性可以互相推出，二者都源自皮亚诺公理。）

提出者

1654 年提出布莱兹·帕斯卡

用到此定理的主题

数学归纳法

分步证明

该定理暂无分步证明。

参考文献

  1. Kenneth H. Rosen (2012). Discrete Mathematics and Its Applications
  2. George Pólya (1954). Induction and Analogy in Mathematics