摘要：数学归纳法是一种非常重要的数学方法，它不仅对我们数学的学习有着很大的帮助，而且在计算机学科的研究中也是一种重要的方法。首先必须准确的理解其意义以及熟练的掌握解题步骤，而在三个步骤中运用归纳假设尤为关键，运用归纳假设推出猜想最为重要。最后我们在通过用数学归纳法证明文法语言的过程中，可以更加深刻理解和掌握“归纳——猜想——证明”这一探索发现的思维方法。
　　关键词：归纳法；计算机科学；计算机应用
　　中图分类号：TP301 文献标识码：A文章编号：1007-9599 (2011) 09-0000-01
　　The Application of Induction in Computer Subgect
　　Liu Lei
　　(Tianjin Polytechnic University,School of Computer Science&Software Engineering,Tianjin300160,China)
　　Abstract:Mathematical induction is a very important mathematical method,it not only to our mathematics learning has the very big help,and in computer subjects also is a kind of important method.Must first understand its meaning of mastering and solving steps,and in three steps that use inductive was key,use inductive hypothesis that the most important launch.Our last through the use mathematical induction prove grammar in the process of language, we can get a more profound understanding and mastering"induction- guess-proof"this exploration of the way of thinking.
　　Keywords:Induction;Computer science;Computer application
　　一、问题的提出
　　设有文法G[A]：A：：=bA|a，则该文法所确定的语言是L（G[A]）={bia|i>=0}.
　　证明（1）：n=1时，A=>*a。
　　n=2时，A=ba。
　　..........................
　　如此证明下去，没有尽头。你可以证明n=1000时，结论成立，但你不能保证n=1001时，A=>b1000a。但我们发现，只要我们能证明n=1000时，结论成立，即A=>b999a.由A=bA得A=bb999a=b1000a—n=1001也必成立。从而这种现象具有一般性。从而我们得出n=k时结论成立，则n=k+1时结论也会成立。因此我们想到另一种证明方法如下：
　　假设：n=k时，结论成立。如果我们能够通过证明得到此时n=k+1也成立，则假设是正确和成立的。下面我们通过另一个哲学上的例子，来进行一个形象化的诠释：
　　一只大老鼠第一次生产，生下一只小老鼠。从而我们可以这样认为，大老鼠生下的的都是小老鼠。为了证明这个猜想，我们假设大老鼠第n次生产，产下的是小老鼠，而不是小猫。如果我们利用这只大老鼠第n次产下的小动物能够证明出它第n+1次生产生下的也是小老鼠。那么，我们可以不怀疑地说：大老鼠生下的都是小老鼠。
　　在上面的例子中，我们可以假设n=k时，结论成立。即A=>*bk-1a；
　　让n=k+1，利用A=>bA和上一步的的结论A=>*bk-1a，我们得到A=>*bka；
　　综上所述，根据归纳法的原理，结论对一切n>=1是成立的。
　　二、数学归纳法概念
　　数学归纳法是一种先得出首个例子的正确性，而后通过递推的方式证明命题是否正确的一种方法.常用来证明与自然数n有关的相关命题。
　　三、数学归纳法的步骤
　　数学归纳法步骤严谨，如果把要证明的命题记作P（n），那么数学归纳法的步骤为：
　　（1）证明当n取对命题适用的第一个自然数n1时，p（n1）正确。
　　（2）假设n=k（ 且k大于等于零）时，命题成立，即p（k）正确.证明当n=k+1时命题成立。
　　（3）根据（1）、（2）当k大于等于零且 时，即p（n）正确。
　　运用数学归纳法证题时，以上三个步骤缺一不可，步骤（1）时正确的奠基步骤，称之为归纳基础，步骤（2）反应了无限递推关系，即命题的正确性具有传递性，若只有步骤（1），而无步骤（2），只是证明了命题在特殊情况下的正确性是不完全归纳法，若只有步骤（2），而没有步骤1，那么假设n=k成立，就时没有根据的，缺少递推的基础，也无法进行递推，有了步骤（1）和步骤（2）使递推成为了可能，步骤（3）是将步骤（1）步骤（2）结合完成数学归纳法中递推的全过程，因此三个步骤缺一不可。
　　最简单和常见的数学归纳法证明方法是证明当n属于所有自然数时一个表达式成，这种方法是由下面两步组成：递推的基础：证明当n=1时表达式成立。递推的依据：证明如果当n=m时成立，那么当n=m+1时同样成立。（递推的依据中的“如果”被定义为归纳假设。不要把整个第二步称为归纳假设。）这个方法的原理在于第一步证明起始值在表达式中是成立的，然后证明一个值到下一个值的证明过程是有效的。如果这两步都被证明了，那么任何一个值的证明都可以被包含在重复不断进行的过程中。
　　四、结论
　　数学归纳法主要是针对一些自然N的相关命题，所以在证明和自然数N有关的恒等式子中有着不可替代的作用，对于一些和自然数N有关的长式子、繁式子都有化长为短、化繁为简的功效.用数学归纳法证明数学问题时，要注意它的两个步骤缺一不可，第一步是命题递推的基础，第二步是命题递推的依据，也是证明的关键和难点，两个步骤各司其职，互相配合，同时，数学归纳法的证明步骤与格式的规范是数学归纳法的特征，如n= 时的假设是第二步证明的“已知”步证明时一定要用到它，否则就不是数学归纳法。计算机学科中数学的归纳法的应用比比皆是，因此熟练的掌握数学归纳法的使用将对计算机学科的应用大有裨益。