数学归纳法(英语:Mathematical Induction,缩写:MI)是一种数学证明方法,通常被用于证明某个给定命题在整个或者局部自然数范围内成立。除了自然数以外,广义上的数学归纳法也可以用于证明一般良基结构,例如:集合论中的树。这种广义的数学归纳法应用于数学逻辑和计算机科学领域,称作结构归纳法。
虽然数学归纳法名字中有“归纳”,但是数学归纳法并非逻辑上不严谨的归纳推理法,它属于完全严谨的演绎推理法。[1]事实上,所有数学证明都属于演绎推理方法。
最简单和常见的数学归纳法是证明当
等于任意一个自然数时某命题成立。证明分下面两步:
骨牌一个接一个倒下,就如同一个值到下一个值的过程
- 证明 “当
时命题成立。”(选择数字1因其作为自然数集合中的最小值)
- 证明 “若假设在
时命题成立,可推导出在
时命题成立。(
代表任意自然数)”
这种方法的原理在于:首先证明在某个起点值时命题成立,然后证明从一个值到下一个值的过程有效。当这两点都已经证明,那么任意值都可以通过反复使用这个方法推导出来。把这个方法想成多米诺骨牌效应也许更容易理解一些。[2][3]例如:你有一列很长的直立着的多米诺骨牌,如果你可以:
- 证明 “第一张骨牌会倒。”
- 证明 “只要任意一张骨牌倒了,其下一张骨牌也会因为前面的骨牌倒而跟着倒。”
则可下结论:所有的骨牌都会倒下。
证明下面这个给定公式(命题)为真:
其中
为任意自然数。这是用于计算前n个自然数的和的简单公式。
第一步是验证这个公式在
时成立。左边
,而右边
,所以这个公式在
时成立。第一步完成。
第二步证明假设
时公式成立,则可推理出
时公式也成立。 证明步骤如下。
假设
时公式成立。即
【等式
】
然后在等式等号两边分别加上
得到
【等式
】
这就是
时的等式。
现在需要根据等式等式
演绎出等式
的符号形式。(需要注意的是如果给定公式不为真,则做不到)通过因式分解合并(形式变换/字符操纵),等式
的右手边
也就是说
这样便证明了从等式
成立可推理出等式
也成立。证明至此完成,结论:对于任意自然数
,
均成立。
在这个证明中,推理的过程如下:
- 首先证明命题
成立,即公式在
时成立。
- 然后证明从命题
成立可以推演出命题
也成立。【此部实际属于演绎推理法。技术方法是基于命题
的符号形式变换出命题
的符号形式。】
- 根据上两条从命题
成立可以推理出命题
,也就是命题
成立。
- 继续推理,可以知道命题
成立。
- 从命题
成立可以推导出命题
也成立。
- 不断的重复推导下一命题成立的步骤。(这就是所谓“归纳”推理的地方)
- 我们便可以下结论:对于任意自然数
,命题
成立。
证明对于Fibonacci数列,定义
,且
,则
。
首先,我们先使得
的情况成立,
然后,我们假定
的情况下的成立的,
然后我们使得
的情况也成立,(这是为了表明,如果有任意数k使得其成立,则有其+1也成立)
于是我们得证,即从
,到
到所有正实数都成立,就像多米诺骨牌的第一块
成立而且每一块的下一块都成立(
)
在应用中,数学归纳法常常需要采取一些变化来适应实际的需求。下面介绍一些常见的数学归纳法变体。
第一种情况:
如果欲证明的命题并不是针对全部自然数,而只是针对所有大于等于某个数字b的自然数,那么证明的步骤需要做如下修改:
- 第一步,证明当
时命题成立。
- 第二步,证明如果
(
) 成立,那么可以推导出
也成立。
用这个方法可以证明诸如“当
时,
这一类命题。
第二种情况:
如果欲证明的命题针对全部自然数,但仅当大于等于某个数字b时比较容易证明,则可参考如下步骤:
- 第一步,证明当
时命题成立。
- 第二步,证明如果
(
)成立,那么可以推导出
也成立。
用这种方法可以证明一些需要通过放缩来证明的不等式。
如果我们想证明的命题并不是针对全部自然数,而只是针对所有奇数或偶数,那么证明的步骤需要做如下修改:
奇数方面:
- 第一步,证明当
时命题成立。
- 第二步,证明如果
成立,那么可以推导出
也成立。
偶数方面:
- 第一步,证明当
或2时命题成立。
- 第二步,证明如果
成立,那么可以推导出
也成立。
或调整命题表述,使之变为对所有正整数成立,例如
- 证明“
对所有正奇数
成立”等价于证明“
对所有正整数
成立”。
又名递降归纳法。数学归纳法并不是只能应用于形如“对任意的
”这样的命题。对于形如“对任意的
”这样的命题,如果对一般的
比较复杂,而
比较容易验证,并且我们可以实现从
到
的递推,
的话,我们就能应用归纳法得到对于任意的
,原命题均成立。
另一个一般化的方法叫完整归纳法(也称第二数学归纳法或强归纳法),在第二步中我们假定式子不仅当
时成立,当
小于或等于
时也成立。这样可以设计出这样两步:
- 证明当
时式子成立.
- 证明当
时成立,那么当
时式子也成立.
例如,这种方法被用来证明:
![{\displaystyle \mathrm {fib} (n)={\frac {\Phi ^{n}-\left(-\Phi \right)^{-n}}{5^{\frac {1}{2}}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/449fcf38d9abca2cb3cecdd4d6a5d62386d6ae2f)
其中
是第
个斐波纳契数和
(即黄金分割)。如果我们可以假设式子已经在当
和
时成立,从
之后可以直截了当地证明当
时式子成立.
这种方法也是第一种形式的特殊化:
- 定义
是我们将证的式子,
和
成立
在
和
成立时成立。
结论:
对一切自然数
成立。
最后两步可以用这样一步表示:
- 证明如果式子在所有的
成立,那么式子在当
时也成立。
实际上这是数学归纳法的大多数通式,可以知道他不仅对表达自然数的式子有效,而且对于任何在良基集(也就是一个偏序的集合,包括有限降链)中元素的式子也有效(这里"
"被定义为
当且仅当
和
)。
这种形式的归纳法当运用到序数(以良序的和一些的良基类的形式)时被称为超限归纳法,它在集合论、拓扑学和其他领域是一种重要的方法。
要区别用超限归纳法证明的命题的三种情况:
是一个极小元素,也就是没有一个元素小于![{\displaystyle m}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc)
有一个直接的前辈,比
小的元素有一个大的元素
没有任何前辈,也就是
是一个界限序数.
参见数学归纳法的三种形式。
二阶逻辑可捕捉数学归纳法这概念,表达成如下逻辑式:
,
是容纳一自然数的述词变元,遍历所有述词而非个别数字,为二阶量词(是故此式与二阶逻辑有关),
与
则是自然数变元,遍历所有自然数。
白话解释此式,此式说:起始步骤
与推递步骤(即归纳假设,
蕴涵
) 两步成立会导出对任一自然数
,
成立之结论。通常,我们为了证明第二步,会假设
成立(归纳假设),再进一步证明
。此牵涉到条件证法,将条件句之前件作为假设,假定其正确以便于证明。
若用一阶逻辑将数学归纳法公设化,则须采用公设模式,替每一个可能存在的述词设下针对其的独立公设。举例而言,我们仅允许三个一阶述词存在,分别名为
、
、
,则原先以二阶逻辑描述的公设可改写为:
,
,
,
。然而其强度与以二阶逻辑描述之逻辑式不同,前者较后者弱。理由为一阶逻辑述词之数量为可数,而二阶逻辑量限所迭代的集合为不可数。
此外,二阶逻辑所表示的归纳公设综合其它皮亚诺公设为同畴(categorical),且所得之自然数模型无限大。根据勒文海姆-斯科伦定理,用一阶逻辑表达的理论若有可数无限大的模型,则其有不可数大的模型,是故无法前头将所述的模型公设化[4]。亦即,用二阶逻辑表达的公设仅允许一群模型彼此同构,而一阶逻辑模型则因前述定理,并非每个模型都同构。
一阶ZFC集合论不允许述词被遍历, 但我们可以借由遍历集合,绕过一阶逻辑之限制,描述归纳法:
![{\displaystyle \forall A{\Bigl (}0\in A\land \forall k\in \mathbb {N} {\bigl (}k\in A\to (k+1)\in A{\bigr )}\to \mathbb {N} \subseteq A{\Bigr )}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4757318e068a3d55ce71fb1205b13ca936b2a392)
本身是集合,但可视作命题——只要命题在这数下成立,数字就会收入集合。别于皮亚诺公设,将数学归纳法定为公设,ZFC集合论直接定义自然数,使得归纳法本身是定理而非公设。
皮亚诺公理视数学归纳法不证自明,设作公理,而于策梅洛-弗兰克尔集合论,数学归纳法可从良序定理推导出来。[5] 需要注意的是数学归纳法只能判定给定命题的真,而不能证伪,因为在形式变换这一过程需要一定技巧与灵感。抽象的概念如自然数,可通过抽象的工具去处理。通过有限的步骤处理无限的对象如证明素数的无穷。