数学归纳法

From 皮果维客

数学归纳法是一种数学证明方法,典型地用于确定一个表达式在所有自然数范围内是成立的或者用于确定一个其他的形式在一个无穷序列是成立的. 有一种用于数理逻辑和计算机科学广义的形式的观点指出能被求出值的表达式是等价表达式; 这就是著名的结构归纳法.

已知最早的使用数学归纳法的证明出现于 Francesco Maurolico 的 Arithmeticorum libri duo (1575年)。Maurolico 证明了前 n 个奇数的总和是 n²。

最简单和常见的数学归纳法证明方法是证明当n属于所有自然数时一个表达式成立,这种方法是由下面两步组成:

递推的基础: 证明当n = 1时表达式成立.
递推的依据: 证明如果当n = m时成立, 那么当n = m + 1时同样成立. (递推的依据中的"如果"被定义为归纳假设. 不要把整个第二步称为归纳假设.)

这个方法的原理在于第一步证明起始值在表达式中是成立的,然后证明一个值到下一个值的证明过程是有效的. 如果这两步都被证明了,那么任何一个值的证明都可以被包含在重复不断进行的过程中.或许想成多米诺效应更容易理解一些; 如果你有一排很长的直立着的多米诺骨牌那么你可以确定:

第一张骨牌将要倒下.
只要某一个骨牌倒了,与他相临的下一个骨牌也要倒.

那么你就可以推断所有的的骨牌都将要倒.

例如

假设我要证明这个式子:

<math>1 + 2 + 3 + \cdots + n = \frac{n(n + 1)}{2}</math>

n属于所有非負整数. 这是一个简单的求和公式,把一直到n的所以自然数相加. 这个式子(n属于所以自然数)的证明过程如下.

[编辑]

证明

設命題P(n)為"<math>1 + 2 + \cdots + n = \frac{ n (n + 1)}{2} </math>"

當n為1,

L.H.S. = 1

R.H.S. = <math>\frac{1(1 + 1)}{2} = 1</math>

因此 P(1) 成立.

现在我们还要证明当n = m处理, 然后证明当n = m + 1时也成立. 可以象下面一样完成.

假设P(m) 成立, 也就是,

<math> 1 + 2 + \cdots + m = \frac{m(m + 1)}{2}</math>

當 n 為 m+1,

L.H.S. = <math>1 + 2 + \cdots + m + (m + 1) = \frac{m(m + 1)}{2} + (m+ 1)</math>

用代数方法处理式子得出

<math>

= \frac{m(m + 1)}{2} + \frac{2(m + 1)}{2} = \frac{(m + 2)(m + 1)}{2} </math>

因此我们可以得到:<math>1 + 2 + \cdots + (m + 1) = \frac{(m + 1)[(m + 1) + 1]}{2} </math>

=R.H.S.

因此P(n+1)成立

從數學歸納法,P(n)成立當n屬於所有非負整數

[编辑]

解釋

这是当n = m + 1时的式子. 可以注意到: 我们做了一个假设是P(m) 成立, 然后我们用这个假设得出P(m + 1). 我们得象征性地写出:

<math>P(m) \Rightarrow P(m + 1)</math>

然而在归纳法中我们可以推断出当n属于所有自然数时式子P(n)成立 :

我们先有P(1)成立, 然后可以得出 P(2)
接着一样地P(2)成立, 得出P(3)成立
... 等等

[编辑]

特殊的方法

[编辑]

从b开始

这种方法在几种形式中不能适用. 例如, 如果我们证明一个不是针对所有自然数的式子,而是仅仅到一个等于或者大于一个确定的数b,那么以下的步骤足够了:

证明当n = b时成立.
证明如果当n = b时成立那么当n = b + 1式子也成立.

例如,这种方法用来证明当n ≥ 3时 n² > 2n 成立. 注意到这种数学归纳法的形式实际上是前面形式的一种特殊情况,因为如果我们打算证明的式子是P(n) 那么用这两条规则等价于用前两步证明当n属于自然数时P(n + b).

[编辑]

假定更小的值成立

另一个一般化的方法叫完全归纳法, 在第二步中我们假定式子不仅当n = m时成立,当n小于或等于m时也成立. 这样可以设计出这样两步:

证明当n = 0时式子成立.
证明当 m ≤ b 时成立,那么当n = m + 1时式子也成立.

例如,这种方法被用来证明:

fib(n) = [Φⁿ − (−1/Φ)ⁿ ] / 5^1/2

fib(n) 是第n个斐波纳契数和 Φ = (1 + 5^1/2) / 2 (即黄金分割). 如果我们可以假设式子已经在当 m and m − 1时成立,从 fib(m + 1) = fib(m) + fib(m − 1)之后可以直接了当地证明当m + 1 时式子成立.

这种方法也是第一种形式的特殊化:

定义 P(n) 是我们将证的式子,

接着用这个规则证明也就是等价于证明

式子用开始两步证明当n属于自然数时, '所有的m ≤ n 存在时 P(m) 成立 '

[编辑]

超限归纳法

最后两步可以用这样一步表示:

证明如果式子在所有的 n < m 成立,那么式子在当n = m时也成立.

实际上这是数学归纳法的大多数通式,可以知道他不仅对表达自然数的式子有效,而且对于任何在良基集(也就是一个偏序的集合,包括有限降链) 中元素的式子也有效(这里 "<" 被定义为 a < b 当且仅当 a ≤ b 和 a ≠ b).

这种形式的归纳法当运用到序数(以有序的和一些的良基类的形式)时被称为超限归纳法. 他在集合论, 拓扑学和其他领域是一中重要的方法.

要区别用超限归纳法证明的命题的三种情况:

m 是一个极小元素,也就是没有一个元素小于m
m 有一个直接的前辈,比m小的元素有一个大的元素
m 没有任何前辈,也就是 m 是一个界限序数.

参见数学归纳法的三种形式.

[编辑]