数学归纳法及其在图论中的应用.doc

数学归纳法及其在图论中的应用

———————————————————————————————— 作者：
———————————————————————————————— 日期：

2

个人收集整理 勿做商业用途
莆 田 学 院

毕 业 论 文

题 目数学归纳法及其在图论中的应用

学生姓名 余晶晶

学 号 510401425

专 业 数学与应用数学

班 级 数本054

指导教师 陈梅香

二00九年五月十日

目 录
0引言…………………………………………………………………(1）
1数学归纳法的理论基础……………………………………………(2）
1.1数学归纳法的理论基础是公理………………………… (2）
1。2第一数学归纳法…………………………………………………（2）
2数学归纳法的基本步骤……………………………………………（2)
2。1 的取值…………………………………………………………（2）
2。2验证初值…………………………………………………………（3)
3数学归纳法的其他形式……………………………………………（4）
3。1第二数学归纳法…………………………………………………(4）
3.2跳跃数学归纳法…………………………………………………(4）
3.3反向数学归纳法…………………………………………………（6）
3.4二重数学归纳法…………………………………………………（7）
4数学归纳法原理在图论中的应用…………………………………（8）
4.1对顶点数进行归纳证明…………………………………………(8）
4.2 对边数进行归纳证明……………………………………………（9）
4。3 对顶点集(或边集)的子集中的元素个数进行归纳证明……(9)
4.4图论中其他与自然数有关命题的归纳证明……………………（10）
结束语…………………………………………………………………（12）
致谢……………………………………………………………………（13）
参考文献………………………………………………………………（13）

数学归纳法及其在图论中的应用
余晶晶
（数学与应用数学 指导老师：陈梅香）
摘 要：本文介绍了数学归纳法原理的两个基本步骤，以及由它的基本原理推导出的数学归纳法的其他四种形式,包括：第二数学归纳法、跳跃数学归纳法、反向数学归纳法、二重数学归纳法,并给出这四个数学归纳法及其应用，并应用数学归纳法、证明图论中的图的顶点数、边数、顶点集或边集、距离、途径等等各个方面与自然数n有关的命题。
关键词：数学归纳法 形式 归纳假设 基本步骤 图论
Abstract:This paper introduces the principle of mathematical induction of the two basic steps, as well as the basic principles of it deduce the mathematical induction of the other four forms， including: Second mathematical induction, jumping mathematical induction ， reverse mathematical induction， double mathematical induction， and gives the theorem of the four mathematical induction and its applications, and prove some proposition about natural number by mathematical induction in graph theory, such as the proposition about vertices of the graph， edge, vertex set or edge set, distance， and so on in graph theory。个人收集整理，勿做商业用途个人收集整理，勿做商业用途
Keywords: mathematical induction form inductive assumption basic step graph theory
0引 言
数学归纳法是用来证明某些与自然数有关的数学命题的一种推理方法。严格意义上的数学归纳法产生于16世纪以后，意大利数学家莫罗利科首先对与自然数有关的命题作了深入的考察。意大利数学家（1858-1932）于1889年在其著作《算数原理新方法》中提出了著名的自然数公理体系,其中欧冠的“归纳公理”成为数学归纳法的理论依据［1］。数学归纳法是数学中的一个重要的证明方法，也是中学数学的一个重要内容。数学归纳法的发展几乎经历了整个数学的发展历程,从而也从一个侧面给出数学发展的缩影。数学归纳法的产生、发展和确立的历史，一定程度上反映了数学产生与发展的历史，而且这是与人类文明的进程休戚相关，同时也显示出人们认识世界、改造世界的力量。数学归纳法的产生经历了一个较长的历史时期。在中学数学中的许多重要结论：如等差数列、等比数列的通项公式与前项和公式、二项式定理都可以利用数学归纳法进行证明。在实际问题中由归纳、猜想得出的一些与正整数有关的数学命题，通过用数学归纳法加以证明,可以使学者对有关知识的认识更加深入，理解更加透彻。运用数学归纳法可以证明许多数学命题，通过这些命题的证明,既可以开阔学者的眼界，又可以使他们受到推理论证的良好训练。数学归纳法在今后的数学研究过程中经常用到,它是很重要的一种数学工具。因此，掌握数学归纳法，研究数学归纳法及其应用具有重要的意义.图论以图为研究对象，包括点、边、面、距离与自然数联系密切,图论中的许多定理在证明的时候，运用数学归纳法证明，能起到化繁为简，避免证明过程复杂的作用。个人收集整理，勿做商业用途个人收集整理,勿做商业用途
数学归纳法是一种常用的不可缺少的推理论证方法，没有它,在图论中很多与自然数有关的命题难以证明.同时对于与自然数有关的命题,把所取的无穷多个值一一加以验证时不可能的，用不完全归纳法验证其中一部分又很不可靠，数学归纳法则是一种用有限步骤证明与自然数有关的命题的可靠方法，不仅思路清晰,大大降低了问题的复杂性,又能找出相应的递推关系,非常奏效。因此，图论中的很多命题的论证，数学归纳法不失为一种行之有效的方法。
处理数学问题时，经常涉及到关于任意正整数成立的一些命题，这些命题实质上是由无限个取具体整数时得到的无限个命题组成的.我们不能逐一验证，此时数学归纳法往往是一种十分有效的方法。数学归纳是一种重要的推理方法。它是与自然数有关的数学命题,依据数学归纳法原理,可以得到可靠的结论的一种归纳推理方法，称作完全归纳法又称数学归纳法。数学归纳法有它因有的理论基础， 运用起来有确定的程式和步骤，有灵活多变的技巧，又和数学各个部分有着广泛紧密的联系。
1 数学归纳法的理论基础
假使我们证得特殊命题,成立，用不完全归纳法，断言对于所有自然数，命题都成立. 这样的论断是不可靠的。 而用完全归纳法进行列举,往往又不可能. 数学归纳法正是解决这类矛盾的一种推理方法，数学归纳法从本质上说是一种演绎推理的方法，但又不能和归纳推理等同。
一个和自然数有关的命题，我们记，如果它实际上是一个包含无数个特殊命题, 这命题序列即而且每一个特殊命题均可由它的前一个命题导出。对于这类命题的证明，我们通常要用到数学归纳法。
1.1 数学归纳法的理论基础是公理［2]
公理：如果某一自然数的集合满足：
①②若自然数， 则。那么,集合就是所有自然数所构的集合。
把这个公理应用于自然数有关的命题序列的证明，设使命题成立的自然数集合是。就得到数学归纳法：
1.2第一数学归纳法［3]
设是一个表示与正整数有关的命题。
归纳奠基：当()时，成立；
递推的依据：假设当时,成立,由此可推出在时成立，那么对一切正整数时都成立。
说明 数学归纳法中的两步缺一不可，第一步验证成立是奠基，第二步利用归纳假设(第二步中的“假设”被定义为归纳假设，不要把整个第二步称为归纳假设），结合已知的有关数学知识证出成立是递推的依据，这两步对证明命题相辅相成,构成数学归纳法证明过程的逻辑结构，尤为重要的是在证明过程中必须用到归纳假设，这是检验是否用对了数学归纳法的一把尺。
2 数学归纳法的基本步骤
前面已经介绍了数学归纳法的基本步骤：第一步是数学归纳法的推理的基础和根据，如果缺了第一步，即使证明了第二步，命题也不一定成立。第二步在命题序列中建立了推理链的关系，在成立的前提下，保证了命题序列中递推关系的成立,使推理链一环扣一环，直至对不小于的所有自然数都成立。两步缺一不可，我们应该注意的问题是：
2。1 的取值
以代表奠基步骤:往往从1开始,又不一定从1开始。
例1
分析 ，

证明 ①归纳奠基：当
②归纳递推：假设某个自然数（）时，有。

综合①②，可得结论，对任何自然数5）都有。
2。2 验证初值
作为奠基步骤,有时不止验证一个值。
例2 设数列｛｝满足：
求证
分析 由于题目条件中给出了递推式
，故作为奠基步骤，必须至少检验两个值，即当的和的值，递推才有基础.
证明 ①归纳奠基：
，显然此时等式成立；
②归纳递推:假设当
，

所以当
因此数列{}对任意的正整数有成立。
3 数学归纳法的其他形式
在第一数学归纳法的基础上,可以演变出数学归纳法的其他形式,本文介绍其他四种形式，包括:第二数学归纳法，跳跃数学归纳法,反向数学归纳法，二重数学归纳法。
3。1 第二数学归纳法［3]
设是一个表示与正整数有关的命题 ，
当）时，成立；
假设在时成立,由此可推出在时成立，那么对一切正整数时都成立。
说明 第二数学归纳法是第一数学归纳法的推论，作归纳假设时，假设、 、…、都成立，并在此前提下证出成立，这是区别于第一数学归纳法的地方，有时会给证明带来很大方便。
对于第二数学归纳法在证明数学命题中的应用，我将在本文第四部分给出一个用第二数学归纳法证明图论中命题的例子。
3。2 跳跃数学归纳法[4］
设是一个表示与正整数 有关的命题，
(1）当=1，2时， 和都成立;
(2）假设当时，命题成立，则当时，命题也成立，那么对于一切自然数都成立。
证明 （用反证法)设不是对所有自然数都成立，那么使不成立的自然数集为，根据最小数原理,M中一定存在一个最小的自然数。
由条件（1)可知.由假设可知必成立。由条件（2)可知成立,则也成立，即成立.此与假设不成立相矛盾.
故必对一切自然数都成立.
上述结论可以推广到一般情形，即
设是一个表示与正整数 有关的命题，为某一自然数（)。如果
(1）当
（2)假设当时，命题成立，则当时，命题也成立，
那么命题对一切的自然数都成立。证明过程类似。
例3 试证 适合于

的解得组数等于

分析 当=1时，方程只有一组解,故2时，方程只有两组解，故（2）=2。而方程的解可分为两类：“"和“”，前一类的解只有(，0)故解的组数为1；而后一类的解得组数等于，适合。故方程与上述方程的解组关系为

由递推关系和可总结出公式来.
证明（1）当=1是，方程为,适合条件的解组只有=1，，即(1）=1。
显然满足。
当=2时，方程为，适合条件的解组为：和显然也满足。
（2）假设当是命题成立，即方程的解组为

那么当时方程的解组为

事实上,由分析可知,有，故有

故命题对所有的自然数都成立。
3。3 反向数学归纳法［4]
设表示一个与自然数有关的命题，若
　　（1）对无数多个自然数都成立;
　　（2）假设成立，可推出也成立；
那么对一切自然数都成立。
证明(用反证法）设所有使命题成立的自然数集合为,所有使命题不成立的自然数集合为。如果不是空集,可在中任取一个数，因时无穷集,所以在中总能可以找到一个数。
所以由条件(2）,为真为真为真,经过有限步之后，总可使也为真,这与假设矛盾，即是空集，故命题对所有的自然数都成立。
下面用反向数学归纳法证明一个数学命题。
例4 证明对任何正整数，都不能被121整除。
证明（1）因为所以当时，都不能被121整除。
（2)假设时，能被121整除，即可写成

所以

从而
又
于是有
综合(1),（2）知，对任何正整数，都不能被121整除。
3。4二重数学归纳法[6]
设为与自然数和相关联的命题函数。如果
（1）当
(2）对任一
那么。
证明 对两次运用第二数学归纳法.
当时,命题都成立，事实上,由条件(1），有成立，由条件(2），假设对任意，由第二数学归纳法,命题
。
假设对任一 事实上，由条件（2），对任意的 根据第二数学归纳法，命题证毕。
例5 试证.
证明 设是与自然数相关的命题函数,
（1）当时,有.
（2）假设对任一都成立.
事实上，
。
又.由二重归纳法可知，对任意的。
由以上内容可以看出,数学归纳法有多种形式,但是无论何种形式，其核心都是必不可少的两个基本步骤。对于各种具体问题选用适宜的数学归纳法形式以使两个基本步骤得以实现是解决问题的重要一环.
4 数学归纳法原理在图论中的应用
图论是数学的一个分支，它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。
因为图论中与自然数有关的命题当时容易验证，并且当时如果结论成立，则不难推导出时结论也成立。所以在图论中利用数学归纳法证明某一命题,我们往往采用第一数学归纳法，有时候也用第二数学归纳法。
4。1 对顶点数进行归纳证明
我们给出一个用第二数学归纳法证明图论中定理的例子.
例６［7]　在树中，，利用第二数学归纳法可证明此定理。
证明 任取自然数，对施行归纳
( 1 ) 当时，则此树无边，即,结论成立。
（ 2 ) 假设对所有，结论成立。
由于不含任何回路， 故从中删去一边后，变成两个互不连通的子图。而每个子图则是连通的，故每个子图均为树.设它们分别是
由归纳假设可得

又因为

故有 即当时，结论成立.
因此，对任意的。
对顶点数用数学归纳法的证明的例子，我们再给出有向图知识中的一个定理，并证明之。
例7［12] 无环有向图总存在一个独立集，使得对于的不在中的每个顶点,从的一个顶点出发通过长最多是2的有向路可到达.
证明 对用数学归纳法。
（1)对于定理显然是正确的。
（2)假设对于顶点数小于的所有有向图定理是正确的，并设是的任一顶点。
由归纳假设,在中,存在一个独立集，使得的不在中的每个顶点,从中的一个顶点出发通过长最多为2的有向路可到达。若从出发通过长为2的有向路可到达。因此再这种情形中，，满足所要求的性质。另一方面，若不与的任何顶点相连，因而独立集具有所要求的性质。
图论中的许多命题与顶点有关，其中一些命题的证明我们针对顶点数进行归纳证明，往往比较有效。
４.２　对边数进行归纳证明
例8[8]　(欧拉公式）设是具有个点条边个面的连通平面图,则有

证明 对边数进行归纳证明。
(1）当时，由于是连通图，所以只能是平凡图,结论显然成立。
（2）假设)时,结论成立，当时，对进行如下讨论.
I、若是树,则是非平凡的,因而中至少有两片树叶，设为树叶，令，则的边数，由归纳假设可知
（)
而

II、若不是树，则中含圈，设边在中某个圈上,令＝－，则仍是连通的，且,由归纳假设有，而，，于是

综上所述，对任意的连通平面图，有.
４.３　对顶点集（或边集）的子集中的元素个数进行归纳证明
例9［9]　设是二元正则树，为的分支点数，为各分支点的层数之和,为各树叶的层数之和，则

证明 对分支点数进行归纳。
（1)
(2）设时，结论成立，下面证明时结论也成立。设的高度为,存在树叶,它的层数为，因为是二元正则树，存在的兄弟，的层数也为。设和的父亲为，删除顶点和的树的图形,则也是二元正则图，为的树叶，的层数为－１。设的分支点数为，各分支点层数之和为，各树叶的层数之和为。易得

由归纳假设，在中有下面等式成立：

经过整理有　　　　,证毕。
４.４　图论中其他与自然数有关命题的归纳证明
例10［10]　判别非递增序列是否为树度序列的一个简单方法如下：
　设为个正整数组成的序列　.则存在一个树,其度序列为。
证明 对进行归纳。
（1）当＝１和＝２时，定理显然成立。
（2）假设定理当时成立,证明当时也成立。即证明存在一个阶为的树的度序列为非递增序列＝满足.
首先，中至少有一个数为１,否则，的序列和至少为２（+１）＞２,这与的序列和为２相矛盾。所以我们从中删去和，增加数放在它应该在的位置，得到序列。含有个数，并且序列和为,根据归纳假设得到，存在树的序列为.现向树种增加结点,将与度为的结点连接得到一条新边，如此得到的新树种结点的度为１,原度为的结点度变为。
所以,树的度序列为。证毕.
例11 证明中长为的(）-途径的条数是中的元素。
证明 用数学归纳法证明。
（1)=1时,由邻接矩阵的定义知结论成立.
(2）若-1时结论成立，即

中长为k—1的（）—途径的条数为。下面证明k时结论成立。
令则显然中的任意一条长为的的（）—途径，可看成先经过边到达，然后经（）—途径到达，由定义,于是由归纳假设恰表示长为由出发，经边到达的途径的条数。
故表示长为的（）—途径的条数。
例12[12］ 对于任何正整数，存在不包含三角形的色图。
证明 对用归纳法。
（1）对于和，图具有所要的性质.
（2)假设已经作出具有色数 的不包含三角形的图。设的顶点是从出发如下构作一个新的图:添加个新顶点

图一
。例如,若
。
例13 一个是2连通的，当且仅当的任意两个顶点至少被两条内部不相交的路相连。
证明 若的任意两个顶点至少被两条内部不相连的路所连,则显然，是连通的，并且没有1顶点割。因此是2连通的。
反之，设是2连通图。对之间的距离用第二数学归纳法来证明:任意两个顶点至少被两条内部不相交的路所连。
（1）首先当。由于是2连通的，因此边不是割边,由邦迪著的《图论及其应用》中的定理2.3（的割边当且仅当）［12]可知,它包含在某个圈中。由此推出：被中两条内部不相交的路所连。
(2）现在假设对于距离小于（即）的任意两个顶点定理均成立,并且设.考虑长为条路，并且设是该路上前面的那个顶点。因为由归纳假设可知：在中有两条内部不相交的又因为是2连通的，所以是连通的，并且包含一条设是在中又在中的最后一个顶点(见下图)。由于这样的顶点是存在的；我们不排除的可能性。
不失一般性,可假设两条内部不相交的路,一条由节（从）和节(由），联合组成，另一条由组成。

图二
结束语：
由上述的例子，我们可以看到，在用数学归纳法证明与自然数有关的命题时，两个基本步骤是不可缺少的，否则命题不一定成立.同时，由数学归纳法原理推到出其他形式的数学归纳法形式多样，能够用于证明不同情况下的多种数学命题，可应用适合的数学归纳法进行证明。用数学归纳法证明命题可以降低过程的复杂性，使推理过程简单，清晰，也保证了推理的严谨性，特别是在图论中的众多命题的证明时,使得证明过程简洁明了，而不失严密性，数学归纳法是一种行之有效的证明方法。
致 谢:
本课题在选题及研究过程中都得到了陈梅香老师的悉心指导.着手课题之初,陈老师为我指点迷津，明确了课题研究的方向和内容；课题研究当中,陈老师关心论文进程，精心点拨，帮助我拓宽思路并鼓励我大胆创新。至此，对她表示由衷的感谢。其次，要感谢我们数学系为我们提供的各种优惠条件，比如免费为我们提供数学实验室里的电脑等等。再次,感谢对这篇论文给予我帮助的所有同学，他们在我对论文写作过程中，帮我分析思路，提出看法。
参考文献：
[1]吕孝亮．关于数学归纳法的基础研究［J]．学术论坛前沿，2008，12(1):291。
［2］罗家雄．浅谈数学归纳法在解数学题的技巧和方法［J］．科教文汇,2007,3（1)：65-65.
［3]赵祥枝．方珍。数学归纳法［J]．福建中学数学,2008,9（3）：46—49.
[4]刘世泽．数学归纳法的另外两种形式［J］．数学通报,1988,4（2):32-33.
［5]郑学群．反向数学归纳法[J］．中学数学，1995,6（4):44-46.
[6］李时兴．第一数学归纳法的推广及应用[J］．三明师专学报,1999,5（1）：1-4。
[7］程晓锦．徐秀花。用数学归纳法证明离散数学的有关结论[J]．北京印刷学院学报，2001,9（2）：23-25。
[8］王天成．数学归纳法的逻辑原理及其在图论中的应用［J］．青海师范大学民族师范学院学报,2008,19（1）：66-67。
[9]朴月华．图论及其应用［M]．南京:东南大学出版社，2000:104—106.
［10]李慧霸,王凤芹译．图论的简明教程[M］．北京：清华大学出版社，2005:72—73。
[11]陈美珍．数学归纳法在离散数学中的应用[J］．郧阳师范高等专科学校学报，2004，24(3):19-20.
［12］[美]J。A。邦迪 U.S.R。默蒂．图论及其应用［M]．北京：科学出版社，1976.
13