具有递推关系的推理---数学归纳法：具有递推关系的推理---数学归纳法

令集合A中的元素的个数是可数的，即集合中的元素可以对应于自然数编号，不失一般性，我们直接假定：A={1，2，…，n，…}。我们希望证明命题P对于集合A中的所有元素成立，如果用P(n)表示对应于编号为行的元素命题P，则问题等价于验证所有的编号命题

P(1)，P(2)，…，P(n)，…

成立。从简单枚举法的讨论知道，我们无法完成对于所有编号命题的逐一验证，但是，凭借直观我们可以接受这样的事实：验证P(1)成立，如果假定P(n)成立就可以验证P(n 1)成立，那么，就认为命题P对集合中所有的元素成立。我们举例说明这个直观。

令A是一个自然数集。我们希望用一个算式表示前k个元素的和，即验证算式

1 2 … k=(1/2)k(k 1) (1)

对一切自然数k成立。用P(n)表示命题：当k=n时算式(1)成立。容易验证命题P(1)成立，现在假定命题P(n)成立，希望验证P(n 1)成立.由P(n)成立出发，我们计算如下：

1 2 … n (n 1)=(1/2)n(n 1) (n 1)

=(n 1)(1 n/2)

=(1/2)(n 1)(n 2)

这正是P（n 1）的表达式，这样就完成了对算式(1)的证明，可是，这样证明得到的结果具有一般性吗？这样证明得到的结果是必然的吗？

我们来验证这种证明方法本身的正确性。我们知道，在一般的情况下，从肯定的角度来验证一个方法本身的正确性是比较困难的，一个简捷的方法是利用反证法，假定这个方法不正确，如果能够推导出与一个已知事实矛盾，那么，就可以利用排中律推断这个方法本身是正确的。

假定上述证明方法不正确，那么，必然存在一些自然数，使得命题P不成立，令m是使得命题P(m)不成立的最小的自然数，因为任意一个自然数组，即任何一个自然数的子集都存在最小的元素，所以这个“令”是可能的。因为我们验证了P(1)成立，所以m≥2，即m-1是一个自然数。因为m是使命题不成立的最小的自然数，那么命题P（m-1）就必然成立，这就与我们的证明程序矛盾了，因为我们证明了如果P（m-1）成立则P(m)成立。因此假定是不成立的，这就验证了证明方法的正确性。

我们称这种证明方法为数学归纳法，数学归纳法的标准推理模式如下：

1．验证命题P(1)成立

2．假设命题P(n)成立

3．验证命题P(n 1)成立

/集合A上的命题P成立 (2)

通常称第二步中的假设为归纳假设，因为我们已经证明了通过数学归纳法得到的结论是必然的，所以，数学归纳法是一种演绎的方法。

数学归纳法的核心和难点都在于P(n)→P(n 1)这个过程的验证，但是，对于命题P(1)的验证也是不能忽略的，我们来分析下面的例子，令A是一个自然数集，验证算式

(k 1)-k=2 (3)

这个算式显然是错误的，但我们可以尝试地论证，如果忽略了数学归纳法的第一步会出现什么情况。用P(n)表示算式中的命题：当k=n时算式(3)成立。现在假设P(n)成立，即假设(n 1) -n=2成立，验证命题P(n 1)，计算如下：

(n 2)一(n 1)=(n ) 1-n-1

=(n 1)-n

=2

在假设前提下，上述推理过程是准确无误的。问题出在这个命题的第一步就是不成立的，即命题P(1)：2-1=2不成立。因此，在利用数学归纳法证明问题时，首先验证命题P(1)是必要的，甚至在许多问题中，还应当从P(1)具体地推导出P(2)。这不仅可以进一步核实命题的正确性，还可以在具体推导的过程中直观建立由P(n)到P(n 1)的论证方法。

柯朗

因为上面的例子是简单的，结论的错误也是明显的，我们很自然会怀疑证明的方法的正确性，但是，如果需要证明的问题比较复杂，不认真处理第一步就可能会引发整个证明的混乱。比如，美籍德国数学家柯朗(1888～1972)讨论了下面的例子。仍然令A是一个自然数集，命题P：集合中任意两个元素相等。这是一个荒谬的命题。其“证明”过程比较复杂：

令a和b是集合中任意两个元素，令max{a,b}表示a和b中大的一个，即max{a,b}=a当且仅当b≤a，或者，max{a,b}=b当且仅当a≤b。

首先验证P(1)。因为a和b是自然数，当max{a,b}=1时必然a=b=1，因此命题P(1)成立。

假设命题P(n)成立，即归纳假设成立，现在验证命题P(n 1)。设a和b是使得max{a,b}=n 1成立的集合A中的元素，我们需要验证a=b。令α=a- 1和β=b-1，则max{α，β}=n。由归纳假设可以得到α=β，因此a-b=α-β=0，即a=b，也就是说命题P(n l)成立。由数学归纳法，命题P成立。一个荒谬的结论得到了完整的“证明”，问题出在哪里了呢？请读者自己查找证明中的问题。

事实上，比利用数学归纳法证明问题更重要的是如何得到要证明的结论，比如，如何在证明之前就预测出(1)式等号右边的算式。一般来说，结论不是由数学归纳法推演出来的，而是借助一些具体计算的结杲，通过直观“猜想”出来的，然后用数学归纳法来验证这个猜想，我们通过(1)式及其扩张来分析这个问题。

高斯

因为自然数之和的表达式(1)比较简单，我们还可能看出来结果，比如：当n为偶数时，用1加上n，2加上n- 1，…，如此类推可以得到n/2个n 1;当n为奇数时，类似地可以得到（n-1）/2个n 1，外加一个(n 1)/2。显然，这两种情况都得到自然数的前n个自然数之和为n(n 1)/2。据说，天才的德国数学家高斯( 1777—1855)很小的时候就知道了这个结果。那么，自然数的平方和、立方和的表达式将会怎样呢？

下面分析自然数平方和的表达式，在中学数学教科书上我们知道这个表达式为：

1² 2² ... n²=(1/6)n(n 1)(2n 1) (4)

这个结果很难凭借直观看出来，但我们可以用下面的方法推导出来。因为

2^k 3^k ... (n 1)^k-(1^k 2^k ... n^k) =(n 1)^k-1

我们可以得到

(2^k-1^k) (3^k-2^k) ... [(n 1)^k-n^k]=(n 1)^k-1 (5)

注意到上式左边的一般项为a^k-b^k的形式 ，可以进行因式分解。比如k=3时，可以得到

(n 1)³-n³=3n² 3n 1

这样，当k=3时对(5)式的左边逐项分解，然后合并同类项，则(5)可以变化为：

3(1² 2² ... n²) 3(1 2 ... n) n=(n 1)³ 1

这样通过(1)式的结果就可以得到(4)式。用同样的方法，令k=4，可以得到自然数立方和的表达式为：

1³ 2³ … n³=(1/4)n²(n 1)²

从自然数平方和、立方和表达式的计算过程可以知道，如果用A(k)表示自然数k次方和的表达式，那么利用(5)式就可以形成下面的计算链：

A(1)→…→A(n)

这也是一种递推的论证方法，用这种方法可以得到自然数任何次方和的表达式。

,