作者：未知 来源：月光软件站 加入时间：2005-2-28　月光软件站

************************************************************************************************************************

数学归纳法（Mathematical Induction）

**************************************************************************************************************************

数学归纳法在算法分析中的应用相信不需要我多说了。几乎在所有的算法分析中都需要运用这种极好的方法。在我看来，它实际上是一种对复杂问题的简化，一种把用对一个两个特殊情况的简单的猜测得出普遍性的规律的方法。我们学起来很容易接受，应该在高中就有所接触了，然而我们不得不佩服并感谢发明这种方法的“强人”。

如前面所述，MI的优点在于通过有限的不完全归纳得出普遍的结论。计算机中所遇到的情况通常是对某个范围内的整数有某个命题成立。那么如何利用这种方法来证明结论的正确性呢？通过简单的分析我们就可以得出结论：假设我们要证明当整数n≥2 有结论C（n）成立，我们首先可以证明当n=2的时候C（2）是绝对成立，这显然是个简单的过程，因为2是个相对小的数，这在分析和计算上给我们提供了很大的方便。然后我们可以假设一个重要的结论成立（所谓假设是不需要证明的）假设：当n=k时，C（n）成立，那么我们现在只需要证明当n=k+1的时候C(k+1)也是成立的就可以说明对所有的比2大的整数都有C(n)是成立的。因为k是比2大的任何数，而k+1是紧接k的一个数，这是个无限的过程，将这个过程进行下去就可以得到覆盖整个n≥2条件的范围。而我们在证明C(k+1)正确性的时候可以利用C(k)成立时所产生的结果，这更是一种便利，因为对两个连续数操作，远比对两个没有联系的数操作来的简单。如果用算法的方式对数学归纳法进行描述，下面将是非常权威的论述（以下出自《计算机程序设计艺术》P13）

//algorithm to construct a proof using mathematical induction. //given a positive integer n //output a proof that P(n) is true. Step1.set k <- 1,output P(1) is true. Step2.if k=n,terminate the algorithm,the required proof has been output. Step3.prove P(k+1),output a proof that “If all of P(1),P(2),…P(k) ”are true,then P(k+1) is true.”Also output “we have already proved P(1),P(2)…P(k);hence P(k+1) is true.” Step4.Increase k by 1 and go to step2.

 

**为了加深对数学归纳法的理解，先举一简单的例子如下：证明Fabnacci sequence（注解，定义如下F_n=F_n-₁+F_n-2(n≥2),F(0)=0,F(1)=1）对φ=(1+√5)/2,有

相关软件：