《数学归纳法及其在图论中的应用.doc》由会员分享，可在线阅读，更多相关《数学归纳法及其在图论中的应用.doc（15页珍藏版）》请在金锄头文库上搜索。
1、莆 田 学 院毕 业 论 文 题 目数学归纳法及其在图论中的应用学生姓名 余晶晶 学 号 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
2、）4.3 对顶点集（或边集）的子集中的元素个数进行归纳证明（9）4.4图论中其他与自然数有关命题的归纳证明（10）结束语（12）致谢（13）参考文献（13）余晶晶 数学归纳法及其在图论中的应用数学归纳法及其在图论中的应用余晶晶（数学与应用数学 指导老师：陈梅香）摘 要：本文介绍了数学归纳法原理的两个基本步骤，以及由它的基本原理推导出的数学归纳法的其他四种形式，包括：第二数学归纳法、跳跃数学归纳法、反向数学归纳法、二重数学归纳法，并给出这四个数学归纳法及其应用，并应用数学归纳法、证明图论中的图的顶点数、边数、顶点集或边集、距离、途径等等各个方面与自然数n有关的命题。关键词：数学归纳法 形式 归纳
3、假设 基本步骤 图论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 in
4、duction, 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, distanc
5、e, and so on in graph theory.Keywords: mathematical induction form inductive assumption basic step graph theory 0引 言数学归纳法是用来证明某些与自然数有关的数学命题的一种推理方法。严格意义上的数学归纳法产生于16世纪以后，意大利数学家莫罗利科首先对与自然数有关的命题作了深入的考察。意大利数学家（1858-1932）于1889年在其著作算数原理新方法中提出了著名的自然数公理体系，其中欧冠的“归纳公理”成为数学归纳法的理论依据1。数学归纳法是数学中的一个重要的证明方法,也是中学数学的一
6、个重要内容。数学归纳法的发展几乎经历了整个数学的发展历程,从而也从一个侧面给出数学发展的缩影。数学归纳法的产生、发展和确立的历史，一定程度上反映了数学产生与发展的历史，而且这是与人类文明的进程休戚相关，同时也显示出人们认识世界、改造世界的力量。数学归纳法的产生经历了一个较长的历史时期。在中学数学中的许多重要结论：如等差数列、等比数列的通项公式与前项和公式、二项式定理都可以利用数学归纳法进行证明。在实际问题中由归纳、猜想得出的一些与正整数有关的数学命题，通过用数学归纳法加以证明，可以使学者对有关知识的认识更加深入，理解更加透彻。运用数学归纳法可以证明许多数学命题，通过这些命题的证明，既可以开阔学
7、者的眼界，又可以使他们受到推理论证的良好训练。数学归纳法在今后的数学研究过程中经常用到，它是很重要的一种数学工具。因此，掌握数学归纳法，研究数学归纳法及其应用具有重要的意义。图论以图为研究对象，包括点、边、面、距离与自然数联系密切，图论中的许多定理在证明的时候，运用数学归纳法证明，能起到化繁为简，避免证明过程复杂的作用。数学归纳法是一种常用的不可缺少的推理论证方法，没有它，在图论中很多与自然数有关的命题难以证明。同时对于与自然数有关的命题，把所取的无穷多个值一一加以验证时不可能的，用不完全归纳法验证其中一部分又很不可靠，数学归纳法则是一种用有限步骤证明与自然数有关的命题的可靠方法，不仅思路清晰
8、，大大降低了问题的复杂性，又能找出相应的递推关系，非常奏效。因此，图论中的很多命题的论证，数学归纳法不失为一种行之有效的方法。处理数学问题时，经常涉及到关于任意正整数成立的一些命题，这些命题实质上是由无限个取具体整数时得到的无限个命题组成的。我们不能逐一验证，此时数学归纳法往往是一种十分有效的方法.数学归纳是一种重要的推理方法。它是与自然数有关的数学命题，依据数学归纳法原理，可以得到可靠的结论的一种归纳推理方法，称作完全归纳法又称数学归纳法。数学归纳法有它因有的理论基础， 运用起来有确定的程式和步骤，有灵活多变的技巧，又和数学各个部分有着广泛紧密的联系。1 数学归纳法的理论基础假使我们证得特殊
9、命题，成立，用不完全归纳法，断言对于所有自然数，命题都成立。 这样的论断是不可靠的。 而用完全归纳法进行列举，往往又不可能。 数学归纳法正是解决这类矛盾的一种推理方法，数学归纳法从本质上说是一种演绎推理的方法，但又不能和归纳推理等同。一个和自然数有关的命题，我们记，如果它实际上是一个包含无数个特殊命题， 这命题序列即而且每一个特殊命题均可由它的前一个命题导出。对于这类命题的证明，我们通常要用到数学归纳法。1.1 数学归纳法的理论基础是公理2公理：如果某一自然数的集合满足: 若自然数, 则。那么，集合就是所有自然数所构的集合。把这个公理应用于自然数有关的命题序列的证明，设使命题成立的自然数集合是
10、。就得到数学归纳法:1.2第一数学归纳法3设是一个表示与正整数有关的命题。 归纳奠基：当（）时，成立； 递推的依据：假设当时，成立，由此可推出在时成立，那么对一切正整数时都成立。 说明 数学归纳法中的两步缺一不可，第一步验证成立是奠基，第二步利用归纳假设(第二步中的“假设”被定义为归纳假设，不要把整个第二步称为归纳假设)，结合已知的有关数学知识证出成立是递推的依据，这两步对证明命题相辅相成，构成数学归纳法证明过程的逻辑结构，尤为重要的是在证明过程中必须用到归纳假设，这是检验是否用对了数学归纳法的一把尺。2 数学归纳法的基本步骤 前面已经介绍了数学归纳法的基本步骤：第一步是数学归纳法的推理的基础
11、和根据，如果缺了第一步，即使证明了第二步，命题也不一定成立。第二步在命题序列中建立了推理链的关系，在成立的前提下，保证了命题序列中递推关系的成立，使推理链一环扣一环，直至对不小于的所有自然数都成立。两步缺一不可，我们应该注意的问题是：2.1 的取值以代表奠基步骤：往往从1开始，又不一定从1开始。例1分析 ， 证明 归纳奠基：当归纳递推：假设某个自然数（）时，有。综合，可得结论，对任何自然数5）都有。2.2 验证初值 作为奠基步骤，有时不止验证一个值。例2 设数列满足：求证 分析 由于题目条件中给出了递推式，故作为奠基步骤，必须至少检验两个值，即当的和的值，递推才有基础。证明 归纳奠基：，显然此
12、时等式成立；归纳递推：假设当，所以当因此数列对任意的正整数有成立。3 数学归纳法的其他形式在第一数学归纳法的基础上，可以演变出数学归纳法的其他形式，本文介绍其他四种形式，包括：第二数学归纳法，跳跃数学归纳法，反向数学归纳法，二重数学归纳法。3.1 第二数学归纳法3 设是一个表示与正整数有关的命题 ， 当）时，成立；假设在时成立，由此可推出在时成立，那么对一切正整数时都成立。 说明 第二数学归纳法是第一数学归纳法的推论，作归纳假设时，假设、 、都成立，并在此前提下证出成立，这是区别于第一数学归纳法的地方，有时会给证明带来很大方便。对于第二数学归纳法在证明数学命题中的应用，我将在本文第四部分给出一
13、个用第二数学归纳法证明图论中命题的例子。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）假设当是命题成立，即方程的解组为那么当时方程的解组为事实上，由分析可知，有，故有
