数学归纳法(mathematical induction)是一种证明与自然数相关的定理的方法,它与自然数集合的良序公理等价,且被列入如 Peano 公理等一些和自然数相关的公理当中。数学归纳法有以下几种形式,以下皆假设
是一个与自然数相关(以下将与定理相关的自然数设做
)的命题。
第一数学归纳法[]
若以下两条皆能成立,则命题
对任意的自然数
皆成立:
- 若对
(或其他自然数)时,命题
成立。
- 若对于任意的
,当命题
对
成立时,可推出命题
对
亦成立。
第二数学归纳法[]
若以下两条皆能成立,则命题
对任意的自然数
皆成立:
- 对
(或其他自然数)时,命题
成立。
- 若命题
对任意
成立时,可推出命题
对
亦成立。
第二数学归纳法的变形[]
若以下两条皆能成立,则命题
对任意的自然数
皆成立:
- 对
时,命题
成立。
- 若命题
以及
成立时,可推出命题
成立。
跷跷板归纳法[]
设
和
是关于自然数
的两个命题。如果有以下两点成立,则命题
和命题
对任意的自然数
皆成立。
- 命题
成立;
- 假设
成立可以推出
成立,假设
成立也可以推出
成立。
二重数学归纳法[]
设命题
是与两个独立的自然数
相关的命题。如果有以下两点成立,则命题
对任意的自然数
皆成立。
- 命题
成立。
- 对任意自然数
,假设
成立可以推出
和
都成立。
向后向前归纳法[]
对一个有关正整数
的数学命题
,这个归纳法是如下的方法:
- 命题
成立。
- 假设
成立,去证明
成立。这一步跳跃的递推过程。
- 假设
成立,去证明
成立,这一步是将跳过的命题通过向前归纳的方式证明出来。
- 于是得到
对任意的
都成立。
这个方法是 Cauchy 首次在他的不等式证明中使用的,可用来证明樊畿不等式。
超限归纳法[]
它是将数学归纳法推广到一般良序集上的结果,它是说:
若
为良序集
的一个子集,且对任意的
,由
可推出
,那么
它和一般的数学归纳法的区别是:超限归纳法可以推广到无穷,例如对一个无穷函数空间,归纳过程可以是从一个有限子空间开始,每次向上推一维,最终得到对于整个空间成立的命题。这种归纳法必须依赖于良序公理。