查看“︁数学归纳法”︁的源代码

[[分类:证明方法]]
{{InfoBox
|name=数学归纳法
|eng_name=mathematical induction
}}
{{InfoBox
|name=数学归纳法证明
|eng_name=proof by induction
}}
'''数学归纳法'''('''mathematical induction''', '''MI''')，简称'''数归'''，指通过起始条件和递推步骤来[[证明]][[自然数]]都[[满足（谓词逻辑）|满足]][[谓词]]的一种方法。

通常的获得数学归纳法相当于[[皮亚诺公理]]的第5条公理，即归纳公理。

归纳公理的形式也称为'''第一数学归纳法'''/弱归纳原理('''weak induction''')，此外有另一个等价的形式为'''第二数学归纳法'''/强归纳原理('''complete induction''' / '''strong induction''')。

== 描述 ==

=== 第一数学归纳法 ===

对谓词 <math>p</math> ，若满足：
* '''起始条件'''/'''归纳基础'''('''base case''' / '''initial case''')：<math>p(0)</math>
* '''递推步骤'''/'''归纳步骤'''('''induction step''' / '''inductive step''' / '''step case''')：<math>\forall n (n \in \mathbb{N} \land p(n) \rightarrow p(n+1))</math>
则可证明 <math>p(n)</math> 对全体自然数成立。

=== 第二数学归纳法 ===

对谓词 <math>p</math> ，若满足：
* '''起始条件'''/'''归纳基础'''('''base case''' / '''initial case''')：<math>p(0)</math>
* '''递推步骤'''/'''归纳步骤'''('''induction step''' / '''inductive step''' / '''step case''')：<math>\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>p(n)</math> 对全体自然数成立。

== 变形 ==

如果我们把 <math>q(n)=p(n+k)</math> 看作一个性质，则：
* 归纳基础：<math>p(k)</math>
* 归纳步骤：<math>\forall n (n \geq k \land p(n) \rightarrow p(n+1))</math>
可推出 <math>p(n)</math> 对任意 <math>n \geq k</math> 成立。