User:Dz902/沙盒/数学归纳法

数学归纳法是一种数学证明方法，通常被用于证明某个给定命题在整个（或者局部）自然数范围内成立。除了自然数以外，广义上的数学归纳法也可以用于证明一般良基结构，例如：集合论中的树。这种广义的数学归纳法应用于数学逻辑和计算机科学领域，称作结构归纳法。

需要留意的是，数学归纳法虽然名字中有“归纳”，但是实际上数学归纳法并不属于不严谨的归纳推理法，实际上是属于完全严谨的演绎推理法。

定义

最简单和常见的数学归纳法是证明当 n 等于任意一个自然数时某命题成立。证明分下面两步：

骨牌一个接一个倒下，就如同一个值到下一个值的过程。

这种方法的原理在于：首先证明在某个起点值时命题成立，然后证明从一个值到下一个值的过程有效。当这两点都已经证明，那么任意值都可以通过反复使用这个方法推导出来。把这个方法想成多米诺效应也许更容易理解一些。例如：你有一列很长的直立着的多米诺骨牌，如果你可以：

那么便可以下结论：所有的骨牌都会倒。

假设我们要证明下面这个公式（命题）：

$1+2+3+\cdots +n={\frac {n(n+1)}{2}}$

其中 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+2+\cdots +m={\frac {m(m+1)}{2}}$ （等式 1）

然后在等式等号两边分别加上 m + 1 得到

$1+2+\cdots +m+(m+1)={\frac {m(m+1)}{2}}+(m+1)$ （等式 2）

这就是 n = m+1 时的等式。我们现在需要根据等式 1 证明等式 2 成立。通过因式分解合并，等式 2 的右手边

$={\frac {m(m+1)}{2}}+{\frac {2(m+1)}{2}}={\frac {(m+2)(m+1)}{2}}={\frac {(m+1)(m+2)}{2}}={\frac {(m+1)((m+1)+1)}{2}}.$

也就是说

$1+2+\cdots +(m+1)={\frac {(m+1)((m+1)+1)}{2}}$

这样便证明了从 P(m) 成立可以推导出 P(m+1) 也成立。证明至此结束，结论：对于任意自然数 n，P(n) 均成立。

在这个证明中，归纳推理的过程如下：

在应用，数学归纳法常常需要采取一些变化来适应实际的需求。下面介绍一些常见的数学归纳法变体。

如果我们想证明的命题并不是针对全部自然数，而只是针对所有大于等于某个数字 b 的自然数，那么证明的步骤需要做如下修改：

用这个方法可以证明诸如“当 n ≥ 3 时，n² > 2n”这一类命题。