你的位置:首页 > 操作系统

[操作系统]数学归纳法


定义

最简单和常见的数学归纳法是证明当n等于任意一个自然数时某命题成立。证明分下面两步:
  1. 证明当n= 1时命题成立。
  2. 假设n=m时命题成立,那么可以推导出在n=m+1时命题也成立。(m代表任意自然数)
这种方法的原理在于:首先证明在某个起点值时命题成立,然后证明从一个值到下一个值的过程有效。当这两点都已经证明,那么任意值都可以通过反复使用这个方法推导出来。把这个方法想成多米诺效应也许更容易理解一些。例如:你有一列很长的直立着的多米诺骨牌,如果你可以:
  1. 证明第一张骨牌会倒。
  2. 证明只要任意一张骨牌倒了,那么与其相邻的下一张骨牌也会倒。
骨牌一个接一个倒下就如同一个值接下一个值骨牌一个接一个倒下就如同一个值接下一个值

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

 


 解题要点

数学归纳法对解题的形式要求严格,数学归纳法解题过程中,
第一步:验证n取第一个自然数时成立
第二步:假设n=k时成立,然后以验证的条件和假设的条件作为论证的依据进行推导,在接下来的推导过程中不能直接将n=k+1代入假设的原式中去。
最后一步总结表述。
需要强调是数学归纳法的两步都很重要,缺一不可,否则可能得到下面的荒谬证明:
证明1:所有的马都是一种颜色
首先,第一步,这个命题对n=1时成立,即,只有1匹马时,马的颜色只有一种。
第二步,假设这个命题对n成立,即假设任何n匹马都是一种颜色。那么当我们有n+1匹马时,不妨把它们编好号:
1, 2, 3……n, n+1
对其中(1、2……n)这些马,由我们的假设可以得到,它们都是同一种颜色;
(2、3……n、n+1)这些马,我们也可以得到它们是一种颜色;
由于这两组中都有(2、3、……n)这些马,所以可以得到,这n+1种马都是同一种颜色。
这个证明的错误来于推理的第二步:当n=1时,n+1=2,此时马的编号只有1、2,那么分的两组是(1)和(2)——它们没有交集,所以第二步的推论是错误的。数学归纳法第二步要求n→n+1过程对n=1,2,3……的数都成立,而上面的证明就好比多米诺骨牌的第一块和第二块之间间隔太大,推倒了第一块,但它不会推倒第二块。即使我们知道第二块倒下会推倒第三块等等,但这个过程早已在第一和第二块之间就中断了。
证明2:举例证明下面的定理
 
——等差数列求和公式
第一步,验证该公式在 n = 1 时成立。即有左边=1,右边=  
=1,所以这个公式在n = 1时成立。
第二步,需要证明假设n = m 时公式成立,那么可以推导出n = m+1 时公式也成立。步骤如下:
假设n = m 时公式成立,即  
(等式1)
然后在等式两边同时分别加上m + 1 得到  
(等式2)
这就是n = m+1 时的等式。我们下一步需要根据 等式1证明 等式2 成立。通过因式分解合并,等式2的右边 

也就是


这样我们就完成了由n=m成立推导出n=m+1成立的过程,证毕。
结论:对于任意自然数n,公式均成立。
对于以上例2的分析
在这个证明中,归纳的过程如下:
  1. 首先证明n=1成立。
  2. 然后证明从n=m 成立可以推导出n=m+1 也成立(这里实际应用的是演绎推理法)。
  3. 根据上两条从n=1 成立可以推导出n=1+1,也就是n=2 成立。
  4. 继续推导,可以知道n=3 成立。
  5. 从 n=3 成立可以推导出n=4 也成立……
  6. 不断重复3的推导过程(这就是所谓“归纳”推理的地方)。
  7. 我们便可以下结论:对于任意自然数n,公式成立。

合理性

数学归纳法的原理,通常被规定作为自然数公理(参见皮亚诺公理)。但是在另一些公理的基础上,它可以用一些逻辑方法证明。数学归纳法原理可以由下面的良序性质(最小自然数原理)公理可以推出:
自然数集是良序的。(每个非空的正整数集合都有一个最小的元素)
比如{1, 2, 3 , 4, 5}这个正整数集合中有最小的数——1.
下面我们将通过这个性质来证明数学归纳法:
对于一个已经完成上述两步证明的数学命题,我们假设它并不是对于所有的正整数都成立。
对于那些不成立的数所构成的集合S,其中必定有一个最小的元素k。(1是不属于集合S的,所以k>1)
k已经是集合S中的最小元素了,所以k-1是不属于S,这意味着k-1对于命题而言是成立的——既然对于k-1成立,那么也对k也应该成立,这与我们完成的第二步骤矛盾。所以这个完成两个步骤的命题能够对所有n都成立。
注意到有些其它的公理确实是数学归纳法原理的可选的公理化形式。更确切地说,两者是等价的。