具有递推关系的推理---数学归纳法:具有递推关系的推理---数学归纳法(1)

令集合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)的论证方法。

具有递推关系的推理---数学归纳法:具有递推关系的推理---数学归纳法(2)

柯朗

因为上面的例子是简单的,结论的错误也是明显的,我们很自然会怀疑证明的方法的正确性,但是,如果需要证明的问题比较复杂,不认真处理第一步就可能会引发整个证明的混乱。比如,美籍德国数学家柯朗(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)式及其扩张来分析这个问题。

具有递推关系的推理---数学归纳法:具有递推关系的推理---数学归纳法(3)

高斯

因为自然数之和的表达式(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)很小的时候就知道了这个结果。那么,自然数的平方和、立方和的表达式将会怎样呢?

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

12 22 ... n2=(1/6)n(n 1)(2n 1) (4)

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

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

我们可以得到

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

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

(n 1)3-n3=3n2 3n 1

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

3(12 22 ... n2) 3(1 2 ... n) n=(n 1)3 1

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

13 23 … n3=(1/4)n2(n 1)2

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

A(1)→…→A(n)

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

,