数学归纳法
| 数学归纳法 | |
|---|---|
| 术语名称 | 数学归纳法 |
| 英语名称 | mathematical induction |
| 数学归纳法证明 | |
|---|---|
| 术语名称 | 数学归纳法证明 |
| 英语名称 | proof by induction |
数学归纳法(mathematical induction, MI)，简称数归，指通过起始条件和递推步骤来证明自然数都满足谓词的一种方法。
通常的获得数学归纳法相当于皮亚诺公理的第5条公理，即归纳公理。
归纳公理的形式也称为第一数学归纳法/弱归纳原理(weak induction)，此外有另一个等价的形式为第二数学归纳法/强归纳原理(complete induction / strong induction)。
描述
第一数学归纳法
对谓词 [math]\displaystyle{ p }[/math] ，若满足：
- 起始条件/归纳基础(base case / initial case)：[math]\displaystyle{ p(0) }[/math]
- 递推步骤/归纳步骤(induction step / inductive step / step case)：[math]\displaystyle{ \forall n (n \in \mathbb{N} \land p(n) \rightarrow p(n+1)) }[/math]
则可证明 [math]\displaystyle{ p(n) }[/math] 对全体自然数成立。
第二数学归纳法
对谓词 [math]\displaystyle{ p }[/math] ，若满足：
- 起始条件/归纳基础(base case / initial case)：[math]\displaystyle{ p(0) }[/math]
- 递推步骤/归纳步骤(induction step / inductive step / step case)：[math]\displaystyle{ \forall n (n \in \mathbb{N} \land \forall k (k \in \mathbb{N} \land k \leq n \rightarrow p(k)) \rightarrow p(n+1)) }[/math]
则可证明 [math]\displaystyle{ p(n) }[/math] 对全体自然数成立。
变形
如果我们把 [math]\displaystyle{ q(n)=p(n+k) }[/math] 看作一个性质，则：
- 归纳基础：[math]\displaystyle{ p(k) }[/math]
- 归纳步骤：[math]\displaystyle{ \forall n (n \geq k \land p(n) \rightarrow p(n+1)) }[/math]
可推出 [math]\displaystyle{ p(n) }[/math] 对任意 [math]\displaystyle{ n \geq k }[/math] 成立。