Loading AI tools
来自维基百科,自由的百科全书
数学归纳法是一种数学证明方法,通常被用于证明某个给定命题在整个(或者局部)自然数范围内成立。除了自然数以外,广义上的数学归纳法也可以用于证明一般良基结构,例如:集合论中的树。这种广义的数学归纳法应用于数学逻辑和计算机科学领域,称作结构归纳法。
需要留意的是,数学归纳法虽然名字中有“归纳”,但是实际上数学归纳法并不属于不严谨的归纳推理法,实际上是属于完全严谨的演绎推理法。
最简单和常见的数学归纳法是证明当 n 等于任意一个自然数时某命题成立。证明分下面两步:
这种方法的原理在于:首先证明在某个起点值时命题成立,然后证明从一个值到下一个值的过程有效。当这两点都已经证明,那么任意值都可以通过反复使用这个方法推导出来。把这个方法想成多米诺效应也许更容易理解一些。例如:你有一列很长的直立着的多米诺骨牌,如果你可以:
那么便可以下结论:所有的骨牌都会倒。
假设我们要证明下面这个公式(命题):
其中 n 为任意自然数。这是用于计算前 n 个自然数的和的简单公式。证明这个公式成立的步骤如下。
第一步证明的是这个公式在 n = 0 时成立(即 P(0) 成立)。这里要注意的是 0 = 0,而 0(0 + 1) / 2 = 0,所以这个公式在 n = 0 时成立。证明的第一步完成。
第二步我们需要证明如果假设 n = m 时公式成立(即 P(m) 成立),那么可以推导出 n = m+1 时公式也成立(即 P(m+1) 成立)。证明步骤如下。
我们先假设 n = m 时公式成立。即
(等式 1)
然后在等式等号两边分别加上 m + 1 得到
(等式 2)
这就是 n = m+1 时的等式。我们现在需要根据等式 1 证明等式 2 成立。通过因式分解合并,等式 2 的右手边
也就是说
这样便证明了从 P(m) 成立可以推导出 P(m+1) 也成立。证明至此结束,结论:对于任意自然数 n,P(n) 均成立。
在这个证明中,归纳推理的过程如下:
在应用,数学归纳法常常需要采取一些变化来适应实际的需求。下面介绍一些常见的数学归纳法变体。
如果我们想证明的命题并不是针对全部自然数,而只是针对所有大于等于某个数字 b 的自然数,那么证明的步骤需要做如下修改:
用这个方法可以证明诸如“当 n ≥ 3 时,n2 > 2n”这一类命题。
归纳推理法
演绎推理法
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.