数学归纳法的发展历程及应用.doc

新乡学院2010级毕业论文论文题目：数学归纳法的发展历程及其应用姓 名 学 号 10140302033 所在院系 数学与信息科学系 专业名称 数学教育 指导教师 指导教师职称 副教授 2013 年 04 月 20 日 目录内容摘要2关 键 词2Abstract2Key words21数学归纳法的发展历程31.1数学归纳法的起源 31.2数学归纳法的发展推广4 1.2.1数学归纳法的发展 4 1.2.2数学归纳法的推广 6 2数学归纳法的应用82.1数学归纳法的原理分析9 2.1.1数学归纳法的逻辑原理 9 2.1.2数学归纳法的原理 9 2.1.3数学归纳法的原理分析102.2数学归纳法的探析及应用13 2.2.1数学归纳法的理论依据13 2.2.2数学归纳法的适用范围142.2.3数学归纳法的证题技巧142.2.4数学归纳法的应用15参考文献21致 谢21内容摘要：本篇文章论述了数学归纳法的发展历程及其应用。数学归纳法的原理分析和探析及应用是本篇文章的主要内容。数学归纳法的发展几乎经历了整个数学的发展，从而从侧面给出数学发展的缩影。数学归纳法作为一种工具通常用在证明数学上的猜想，是解数学题最基本和最重要的方法之一，它在数学各个分支(解题、图论、中学数学等)都有着广泛的应用。数学归纳法是数学中一种重要的证明方法，也是中学数学一个非常重要的内容,用于证明与无穷的自然数集相关的命题。关键词：数学归纳法 发展历程 应用 原理分析 中学数学 自然数集Abstract：This article discusses the development history of mathe- matical induction. The principle analysis and analysis and application of mathematical induction is the main content of the paper. The develop- ment of mathematical induction almost witnessed the development of the whole history of mathematics, thus giving the epitome of mathematics from the side. Mathematical induction is one of the fundamental and the most important method of solving math problems, which has a wide range of applications in various branches of mathematics (problem solving, graph theory, secondary mathematics, ect). Mathematical induction is an important method of proof in mathematics and a very important content in middle school mathematics, which is used to prove propositions rel- ated to infinite natural number set.Key words: Mathematical induction Development Application Prin-ciple analysis middle school mathematics Natural number set 221 数学归纳法的发展历程数学归纳法是数学中一种重要的证明方法，也是中学数学一个非常重要的内容，用于证明与无穷的自数集相关的命题但凡涉及无穷，总会花费数学家大量时间与精力，去理解并弄清它的真正意义普通归纳法与自然数这一最古老的数学概念及“无穷”这个无法直观感觉的概念相结合的“数学归纳法”，自然也需要一个漫长的认识过程有限个数字、元素、对象的认识很容易，因为它们很直观，一个个“数”或一个个“考察”即可，当数字、元素、对象多到无数个，即“无限”或“无穷”个时，就不是这么简单数数、看看的事了，因这无穷多的对象是无法完全“摆”出来直观感受的，如果再带上一些复杂的关系，那就更加无法直观反映了在“无穷”多个对象时，较简单的情形就是与自然数相关的“无穷”，比如用P ()表示与自然数有关的无穷多的数字、元素、对象或性质、命题等为了“数”清这无穷多的对象，或“看”清摆不出来的对象是否也带有看得到的对象所具有的复杂关系，那只能用“归纳”的办法去合理地“猜”，这就是普通“归纳法” 的作用，是人类认识未知的一个普遍有效的方法，它是通过少数几个对象所显现的特征，根据后面对象与这少数对象在看得到、感觉得了的“相似”关系中，合理推测这些对象特征的办法这时，也许你运气好恰好“猜”对了，也许没那么好的运气，一而再再而三地猜错，即使你猜对了，对数学家而言也不敢轻易恭维，因为他们需要的是“准确”的计数或“清晰” 地看到性质，也就是说，必须对你的猜测给予严格的证明才能认可如此一来，如何“准确”数、“清晰”看对象或其性质，就成了数学家伤脑筋的一个问题，这一“数”就数了两千多年从普通不严密的“归纳法”发展到精确的“数学归纳法”，再到更一般的“超穷归纳法”、“连续归纳法”1.1 数学归纳法的起源追根溯源，数学归纳法可以在印度和古希腊时代的著作中找到丝缕痕迹，例如，印度婆什迦罗（Bhskara，1114约1185）的“循环方法”和欧几里得素数无限的证明中都可以找到这种踪迹欧几里得几何原本第九卷命题20为：质数比任何指定数目都要多（注：质数也称为素数），即：素数无穷欧几里得对这个命题的证法是经典的他假定素数是有限的，不妨设这有限的个素数为、 、然后作自然数+1，并证明还存在新的素数，从而得到矛盾因为若所作的数是素数，则它比全部给出的个素数都要大，因此是一个新的素数，这与假设有个素数矛盾；又若它不是素数，它必能被一素数整除，但它被已知全部的个素数、 、除都有余数1，故整除+1的素数必定是这个素数以外的新的素数，从而又与假设有个素数的条件矛盾欧几里得素数无穷命题即是说，素数的个数与自然数的个数一样多上述证明可以这样 翻译，首先，至少有一个素数存在，因为2就是素数，这一点在欧几里得的证明中没有指明；此外，上面欧几里得的证明表明，假如有个素数，那么就必定有个素数存在也就是按现代数学归纳法的要求，证明了从到的递推关系，即完成了数学归纳法证明的关键性一步但欧几里得没有使用任何明显的术语与现在的推理格式，因此，我们只能认为它蕴涵了现代数学归纳法的痕迹1.2 数学归纳法的发展推广1.2.1数学归纳法的发展直到十七世纪后，在数学归纳法有了明晰的框架后，各种形式的数学归纳法逐步得到发展，具体使用中的各种变异形式，如奠基步骤中的起始命题证明、归纳步骤中的跳跃台阶设置等都作了相应推广，发展出了最小数原理、第一和第二数学归纳法、反向归纳法、递减归纳法、螺旋归纳法、双重甚至多重归纳法等各种形式的数学归纳法由于分析算术化的需要，数的理论也得到了充分发展，并最终将整个分析建基于自然数之上，至1889年意大利数学家C皮亚诺（CPeano，18581932，意大利）发表 算术原理新方法，给出自然数的公里体系，不仅使全部微积分理论根基于此，也使数学归纳法有了一个准确、合理的理论基础Peano自然数公理系统：1是一个自然数；1不是任何其他自然数的后继；每个自然数的后继是自然数；若两个自然数的后继相等, 则这两个自然数也相等； 若M是由一些自然数所组成的集合，而且1属于 M，且当任一自然数属于M 时，的后继也属于M，则 M 就包含了全部自然数其中公理V被称为归纳公理，是数学归纳法的逻辑基础几乎同时，在分析算术化的过程中，对“无穷”概念作出了深刻的分析，扫除了微积分发展中的主要障碍，并对分析中的“不健康”点（不连续点、不收敛点等）逐渐有了深刻认识，为最终建立实分析奠定了基础在对“例外”的考虑中，康托尔是独具慧眼的数学家，以此为起点，康托尔在 1897年建立了集合论基础，并对自然数作了深入、细致的研究，发明了超穷数，建立了超穷序数与超穷基数理论，并论述了良序集的特别理论，在此基础上将数学归纳法扩展为超穷归纳法我们熟悉的归纳公理用集合论的语言可表述为：设S是自然数集合N的一个子集，如果：（1）1是 S的元素；（2）从是S的元素可推出+ 1是S的元素. 那么，（3）S= N对于良序化的集合也有类似的性质：设 A 是良序化的集合，S 是 A 的一个子集，如果（1）A 的最小元素是 S的元素；（2）是A 的元素，而从所有在A中比小的元素是S的元素可推出也是S的元素. 那么，（3）S= A由彼此相似的良序集确定的数称为序数, 对于这样的良序集和序数相应的有下列超穷归纳法（有些教材或专业书直接将上述命题称为超穷归纳法）：超穷归纳法 设是序数的一个命题，并且满足：如果任给，都成立，则成立那么，任给序数，都成立因为没有序数比0小，所以“任给，都成立”总是真的，因此上述归纳法定理的条件中蕴涵着成立应用时，有时需要特别证明成立如若讨论的是大于等于某个序数的所有序数的性质，这时，与应用普通数学归纳法一样，需要对超穷归纳法条件需要稍加改动上述条件改为：如果任给，都成立，则成立易知，数学归纳法是超穷归纳法的特殊形式，但从数学归纳法不能推出超穷归纳法，因为自然数集只是特殊的良序集，而普通的数学归纳法无法跨越无穷达到“超穷”数学归纳法和超限归纳法是对“离散”的无穷数集作出判断的严格的数学方法对于连续情形，直到上世纪80年代才发现有一个十分简单而又便于掌握与应用的关于实数的归纳法，称为连续归纳原理或连续归纳法：设 P ()为关于实数的一个命题，如果（i）有某个实数，使得对一切实数，有 P ()成立；（ii）若对一切实数 0，使 P ()对一切实数+成立那么，（iii）对一切实数有P()成立连续归纳法与数学归纳法或超穷归纳法形式极为相似，某种程度上表明离散的自然数集或良序集与连续的实数集在一定条件下的统一性连续归纳法可以用来刻画实数系统的连续性公理，并推出一系列关于实数的命题，以及微积分中涉及连续的所有命题，连续归纳法的发现使有关实数的命题变得简单而易于掌握至此，“归纳法”完成了较全面的、数学化的发展，“数学归纳法”在有限与无限之间架起了一座安全的桥梁随着数学对象的进一步扩展，严格、准确的“归纳法”表达形式或许还会有更进一步的发展，因为数学概念的本身就是随着数学的整体发展以及人类认识的不断深化而逐步深入地修改、完善的，文献8用集合论的基本概念、现代数学的术语包括代数结构的语言与逻辑手段阐述数学归纳法，以表明数学归纳法的现代建构及其应用综上所述，“归纳法”的精确化、成熟化几乎伴随了整个数学发展、成熟的历史, 从古代印度数学和古希腊欧几里得几何原本至二十世纪下半叶连续归纳法的发现1.2.2数学归纳法的推广数学归纳法是一个非常常用的数学工具，它在论证有关自然数的命题时十分有用本文中试图将通常适用于自然数系的数学归纳法推广到下有界整数集Z， 与上有界整数集Z，及全体整数集Z作为应用，证明关于二元命题Z的数学归纳法定理1设是与整数，有关的一列命题且满足以下条件：（1）P()成立；（2）成立P(+1)成立，则对任一整数，命题P()都成立证明 定义 Q() = P(+1)，则Q()N 是与自然数N 有关的一列命题且满足以下条件：（1）Q(1)成立；（2）Q() 成立Q(+1)成立因此，由通常数学归纳法可知：N，命题Q()成立，从而Z且，命题P() 都成立推论1 设 P() 是与整数有关的一列命题且满足以下条件：（1）P() 成立；（2）P()成立P(1)成立，则对任一整数，命题P()都成立证明 设Q() = P()，=，则Q ()是与整数有关的一列命题且满足以下条件：（1）Q()成立：（2）Q()成立Q(+1)成立于是，由定理 1知：对任一整数，命题Q()都成立因此，对任一整数，命题P()都成立定理2 设P()Z是与整数Z有关的一列命题且满足以下条件：（1）对某一整数，P() 成立；（2）P()成立P(1)成立，则Z，命题P()都成立证明 由定理1知：Z且，命题P ()成立再由推论1知：Z，且，命题P()都成立. 故Z，命题 P() 都成立定理3设 P(，) ，Z是与整数，Z有关的一列命题且满足以下条件：（1）对某一对整数，P(，)成立；（2）P (，) 成立P(，1)，P 1，)都成立.则对任一整数对(，)Z=ZZ，命题P(，)都成立证明 对任一整数Z，考虑命题：Q()：对任一整数Z，P (，) 成立由于命题P(，)成立，且P(，)成立P(，1)成立，从而由定理2知：Z，命题P(，)都成立.这说明，命题Q()成立设命题Q()成立即Z，命题P(，)都成立从而由条件(2)知：Z，命题P(1，)都成立，即命题Q(1)成立，这就证明了：（1）命题Q()成立；（2）设命题Q()成立，则命题Q(1) 成立因而，由定理2知：Z，命题Q()都成立，即(，)Z= ZZ，命题P(，)都成立类似于定理3之证明，不难证明以下更一般的数学归纳法：定理4 设 P(，) 是与整数组(，)Z有关的命题且满足条件：（1）对某一组整数(，)，命题 P (，) 成立；（2）P(，)成立 P (，) ，P(，)，P(，)都成立，则对任一组整数(，)Z，命题 P(，)都成立2 数学归纳法的应用数学归纳法是一种证明与自然数n有关的数学命题的重要方法，也是一种常用的不可缺少的推理论证方法，没有它，在图论中很多与自然数有关的命题难以证明；同时对于与自然数有关的命题，把n所取的无穷多个值一一加以验证是不可能的，用不完全归纳法验证其中一部分又很不可靠，数学归纳法则是一种用有限步骤证明与自然数有关的命题的可靠方法，其思维方式对于开发学生的智力有重要价值在图论学习中，掌握并应用好这一方法有十分重要的意义本篇文章对数学归纳法的应用我先从其原理入手进行分析，逐步对数学归纳法的逻辑原理、原理分析、理论依据与适用范围和基本形式进行介绍分析，最后再对其应用进行介绍2.1 数学归纳法的原理分析2.1.1 数学归纳法的逻辑原理数学归纳法是一种证明与自然数n有关的数学命题的重要方法我们首先看一个简单的、人们熟悉的归纳集合，即自然数集N=0，1，要确定N，可先给出一个特殊的元素0，称为初始元，它是产生N 的基础然后再给出一个由自然数产生自然的运算，即一元后继运算n（=n+1）这个运算作用在初始元0上得到1，再作用在1上得到2，把这个过程一直继续下去，就可以依次把所有自然数产生出来这个后继运算n有一个性质，即当nN时，则nN。令P是自然数的一个公共性质，并令P（n） 是一个命题，表示自然数n有性质P现在假设命题：（1）P（0）；（2）所有n，如果P（n）成立，则P（n）成立，那么可得：(3) 则所有n，P（n）这就是通常所说的数学归纳法原理，用公式可表示为：P（0）n（nN（p（n）P（n） n（nNp（n）或者表示为：n（nN p（m）（mn）P（n）n（nNp（n）它是数学归纳法（简称归纳证明）的基础根据该原理，我们可在有限的步骤内，证明自然数集中无限的元素都有某性质，即只要证明上述命题（1）和（2），我们就归纳地证明了命题（3）2.1.2 数学归纳法的原理自然科学中的经验归纳法，是从某一现象的一系列特定的观察出发，归纳出支配该现象所有情况的一般规律，而数学归纳法则是迥然不同的另种手段，它用来证实有关无限序列（第一个，第二个，第三个，等等，没有一个情况例外）的数学定理的正确性数学归纳法原理：假设我们希望证明一系列无限个数学命题 A，A，A，它们合在一起便构成一般的命题A如果a）通过某种数学论证可以证明，对于任一整数r，如果命题A已知为真，则命题A随之亦真；b）第一个命题A已知为真，那么序列中所有命题必都为真，从而A得证数学归纳法的原理是奠基在下属事实的基础上：在任一整数 r 之后接着便有下一个 r+1，从而从整数1出发，通过有限多次这种步骤，便能达到任意选定的整数n推广后的数学归纳法原理：假设给定一系列命题 A，A，A，其中S是某正整数，如果a） 对于每个rs，A的正确性可以从A的正确性导出；b）A已知为真，则所有命题A，A，A，均为真；换句话说，对于所有的ns，A为真我们再次强调指出，在自然科学中，数学归纳法原理与经验归纳法是完全不同的，一般的定律如果被证实了任意有限次，那么不论次数多么多，甚至至今尚未发现例外，都不能说该定律在严格的数学意义下被证明了，这种定律只能算作十分合理的假设，它容易为未来的经验结果所修正在数学中，一条定律或一个定理所谓被证明了，指它是从若干作为真理接受的假设出发得到的逻辑推论人们考察一个定理，如果它在许多实例中是正确的，那么就可猜想定理在普遍意义下将是真的；然后人们尝试用数学归纳法以证明之如果尝试成功，定理被证明为真；如果尝试失败，则定理的真伪未定，有待以后用其他方法予以证明或者推翻.因此在应用数学归纳法原理是要牢记 a）和 b）必须真正的满足2.1.3 数学归纳法的原理分析（1）数学归纳法的具体表现形式归纳法分为完全归纳法和不完全归纳法，而数学归纳法属于完全归纳法，它又分为有限数学归纳法和超限数学归纳法，对于后者，在实变函数论中会学到；前者有两种不同的形式，它们分别叙述为：第一数学归纳法：如果性质P（n）在n=1时成立，而且在假设了n=k时性质P（k）成立后，可以推出在n=k+1时性质P（k+1）也成立，那么我们可以断定性质P（n）对一切自然数n都成立第二数学归纳法：如果性质P（n）在n=1时成立，而且在假设了对所有小于或等于 k 的自然数n性质P（n）都成立后，可以推出在n=k+1时性质P（k+1）也成立，那么性质P（n）对一切自然数n都成立下面我们来看第一数学归纳法和第二数学归纳法之间的关系，可以用一个定理说明定理 第一数学归纳法和第二数学归纳法等价证明 假设性质 P(n)在 n=1 时成立，于是化为证明：由P(k)成立，则可以推出 P(k+1)成立的充分必要条件为由 P(n)（其中 nk）成立，可以推出 P(k+1)成立必要性：由已知 由 P(k)成立，则可以推出 P(k+1)成立，假设 nk 时 P(n)成立，特别P(k)成立，所以 P(k+1)成立得证充分性：（反证法证明）由已知nk时P(n)成立，可以推出 P(k+1)成立，于是，由 P(k)成立推不出 P(k+1)成立的所有自然数k构成一非空子集，记m为该子集的最小自然数所以，对任一自然数 n，只要 n1 自然数集N有最小数1 当1A，A有最小数1当1A 时，假设 A 没有最小数构造集合T= xxN 且对aA xa则 1T假设 nT 若 n +1A 则 n +1 为 A 中的最小数与假设矛盾 n +1T那么1T，nT时n+1T由归纳公理T=N，则A=与A为非空集矛盾 N 的任一非空子集中必有一个最小数以上是用归纳公理对最小数原理作证明下面用最小数原理对第二数学归纳法做一个证明第二数学归纳法：设P（n）是一个与自然数有关的命题若下列两个条件成立：（1）P（1）成立；（2）假设P（n）对于所有满足 l表示可吞食）下面考虑 n=k+1 时的情形，即在上面情形里加进一种害虫（当然，我们还可以将k+1种害虫分为两组，一组k种，一组一种，由归纳假设第一组k种可排成，使前一种可吞食后一种，再将第二组的一种记为加入），将有下面两种情形：若，则可将置前，则有 命题为真若，再将与放在一起试验，若，可将置后前即可，这时有 ，命题为真否则可重复往下试验，经过有限次（k次），必有下列情形之一：，问题解决否则，则可置 ak+1于 ak之后.此时有 ，命题亦成立综上，命题对k+1成立，从而对任意自然数（n2）成立2 第二数学归纳法的应用例2 计算行列式分析：该行列式如果直接计算很困难，也很难发现什么规律，但是如果先依最后一行展开，则可得递推公式：2（1）而时，时，2，由此可猜想下面用第二数学归纳法证明证明（1）当时，猜想成立（2）假设时，当时，由式（1），有D= ，故时，有，归纳法完成，故对一切 nN*，都有总之，数学归纳法的两个步骤，缺一不可.即都是必须的，否则将不完整，甚至导出错误的结果例如对于命题若我们放弃验证第一步，而直接证第二步，即设时命题成立，即，而对于时，由(2，即命题对于时亦成立能否由此得到命题正确呢？其实这个命题是错误的.但我们居然推演出了，毛病在于第一步没有验证至于只验证第一步，而不验证第二步，这虽然只是对命题的不完全归纳，但它却无法保证命题的正确3 有关代数恒等式的证明一般采用的证明方法是在等式两边同时加上或同乘以第项，然后适当变形可证得例3 求证：（）证明：（1）当时，左边，右边，所以当时，命题成立（2）假设当()时命题成立，即，将此式的两边同时乘以，得所以当时命题成立综合（1）（2）可知对于任意自然数命题都成立4 有关数列命题的证明例4：求证：等差数列前n项和的公式，其中为首项，为公差证明：（1）当，等式成立（2）假设当()命题成立，即，那么，所以当时命题成立综合（1）（2）可知对于任意自然数命题都成立5 有关不等式的证明早期假设，合理放缩要由“假设不等式”成立推正到“目标不等式”成立，可先尽早使用“假设不等式”，再利用辅助条件通过合理的放缩，逐步向“目标不等式”逼近例5证明不等式：（n）证明：（1）当时，左边，右边，左边右边，不等式成立（2）假设当()不等式成立，即当时，则（现关键证明），即当时，不等式成立综合（1）（2）可知对于任意自然数不等式都成立等价转化，降低难度当给出的不等式不容易直接用数学归纳法证明时，可以对命题进行等价转化，化归为证明相对容易的不等式例6已知数列满足：，且求证：数列对于任何，有成立，或对于任何，有成立证明：（1）当时，结论显然成立（2）假设()结论成立，即，则，即当时，原式成立由（1）（2）可知恒成立，故时，恒成立；同理时，恒成立，即当时，恒成立6 应用数学归纳法证明整除问题应用数学归纳法证明整除问题，是数学归纳法的重要应用之一这类问题涉及到整除性的知识，如果能被整除，那么的倍数也能被整除，如果、都能被整除，那么它们的和或差也能被整除，从整数的基本入手，通过添项去项进行配凑，使之能够获证例7证明能被8整除证明：（1）当时，显然能被8整除，命题成立（2）假设当时，原命题成立，即能被8整除，那么，当时，这里的第一项由归纳假设能被8整除，第二项中为奇数，则为偶数，故第二项4能被8整除，由整除性质可知，它们的差也能被8整除，这就是说：当时命题也成立即原命题对于所有自然数都成立7 数学归纳法在离散数学方面的应用离散数学以离散问题为研究对象，其中很多结论都与自然数有关，并可以用数学归纳法证明离散数学中的某些结论如有关集合中关系及性质、树及其性质，这样既降低了证明过程的复杂性，又是推理过程更加严密清晰例8 已知，是个正整数，已知，证明存在结点度数分别为，的一棵树证明：对结点进行归纳证明，可构造满足条件的树（1）当时，由，而，所以，于是存在为满足条件的树（2）假设当时结论成立，即存在结点度数分别为，的一棵树，要证时，结论也成立由，均为正整数，知这个数中至少有两个为一，否则，与条件矛盾 不妨设，于是，则考虑，这个正整数，由归纳假设知存在结点度数分别是，的一棵树，在中从结点度数为的结点引出一条边，另一端记为，这样得一棵新树，在中deg，deg于是，因此，即为所求的一棵树8 数学归纳法在概率论方面的应用在概率问题中常会遇到一些与试验次数有关的重要结论，这些结论在使用数学归纳法证明时，常常