浅谈数学归纳法及其应用

晋中学院XX学院20XX届本科生毕业论文

浅谈数学归纳法及其应用

学生姓名:XXX（XXX班） 指导老师:XXX

摘 要:数学归纳法是数学中最基本也是最重要的证明方法之一,在数学各个分支里都有广泛应用,利用数学归纳法可以解决比较复杂的问题.本文从数学归纳法的整体结构出发,对数学归纳法的思想渊源、基本原理及常见形式进行了分析总结,介绍了数学归纳法在初等数学、高等数学、离散数学、概率论、图论等学科中的应用. 关键词:数学归纳法;渊源;原理;表现形式;理论基础及其证明;应用

晋中学院XX学院20XX届本科生毕业论文

On the Mathematical Induction and its Application

Student: X XX Instructor: X XX

Abstract: Mathematical induction is one way of the most basic and important mathematical proof, and has a wide application in several mathematics. Using the mathematical induction can solve the complicated problem. This paper begins from the overall structure of mathematical induction. Then mathematical induction on ideological origin, basic theory and common forms are analyzed and summarized. It is introduced by the application of mathematical induction in basic mathematics, discrete mathematics, probability theory, graph theory and other subjects.

Key words: Mathematical induction;Origin;Theory;Manifestations;Theoretical foundation

and its proof;Application

晋中学院XX学院20XX届本科生毕业论文

目 录

1 数学归纳法的思想渊源?????????????????1 2 数学归纳法的原理???????????????????2 3 数学归纳法??????????????????????3

3.1 数学归纳法的具体表现形式???????????????3 3.2 两种归纳法之间的关系?????????????????4

4 数学归纳法的理论基础及其证明?????????????4 4.1 第一数学归纳法的理论基础及其证明???????????4

4.2 第二数学归纳法的理论基础及其证明???????????5

5 数学归纳法在各门学科中的简单应用???????????6 5.1 数学归纳法在初等数学中的应用?????????????6

5.2 数学归纳法在高等代数中的应用?????????????8 5.3 数学归纳法在离散数学方面的应用 ???????????11 5.4 数学归纳法在高等数学中的应用 ????????????12 5.5 数学归纳法在图论中的应用 ??????????????14 5.6 数学归纳法在概率论方面的应用 ????????????14

6 结束语?????????????????????????15 参考文献????????????????????????16

晋中学院XX学院20XX届本科生毕业论文

1 数学归纳法思想的渊源

追根溯源数学归纳法可以在印度和古希腊时代的著作中找到丝缕痕迹,例如,印度婆什迦罗（Bashkiria 1114～约1185）的“循环方法”和欧几里得素数无限的证明中都可以找到这种踪迹.欧几里得《几何原本》第九卷命题20为:质数比任何指定数目都要多（注:质数也称为素数）,即:素数无穷.欧几里得对这个命题的证法是经典的.他假定素数是有限的,不妨设这有限的n个素数为p1,p2,?,pn.然后作自然数

p1,p2,?,pn?1并证明还存在新的素数,从而得到矛盾.因为若所作的数是素数,则它比全部给出的n个素数都要大,因此是一个新的素数,这与假设有n个素数矛盾;又若它不是素数,它必能被一素数整除,但它被已知全部的n个素数p1,p2,?,pn.除都有余数1,故整除p1,p2,?,pn?1的素数必定是这n个素数以外的新的素数,从而又与假设有

n个素数的条件矛盾.

欧几里得素数无穷命题即是说,素数的个数与自然数的个数一样多.上述证明可以这样“翻译”,首先,至少有一个素数存在,因为2就是素数,这一点在欧几里得的证明中没有指明;此外,上面欧几里得的证明表明,假如有n个素数,那么就必定有n?1个素数存在.也就是按现代数学归纳法的要求,证明了从n到n?1的递推关系,即完成了数学归纳法证明的关键性一步.但欧几里得没有使用任何明显的术语与现在的推理格式,因此,我们只能认为它蕴涵了现代数学归纳法的痕迹.

现代形式的数学归纳法被很多人认为是法国数学家、物理学家和哲学家帕斯卡(B?Pascal,错误！未找到引用源。1623～1662)发现的.例如,德国数学家和数学史家M?B?康托尔(M?B?Cantor,1829～1920)在他最重要的著《数学史演讲》卷2第749页中就这样误定,后来他在有关的杂志中作了纠正,他说,华卡(G?Vacca?)先生告诉我,意大利的莫洛里科斯(F错误！未找到引用源。Maurolycus,1494～1575,意大利的数学家、物理学家和工程师)在其1575年出版的著作《算术》中描述并使用了数学归纳法.美国数学史家H错误！未找到引用源。伊夫斯的《数学史概论》（第六版中译本）也认为帕斯卡1665年的论文《三角阵算术》中有数学归纳法的最早的、可被接受的陈述.其实,帕斯卡在给卡卡维(Carcavi卒于1684年)的一封信中已承认是莫洛里科斯引入了这一方法.近代最新研究表明,不仅帕斯卡不是数学归纳法的最早发明人,莫洛

1

晋中学院XX学院20XX届本科生毕业论文

里科斯也不是最早使用这一方法的数学家,可被接受的数学归纳法的使用年代比莫洛里科斯更早,十四世纪法国的数学家、天文学家和哲学家莱维?本?热尔松在其1321年出版的代表作《计算技术》中已经“本质上使用了数学归纳法”,更有资料表明,在中世纪伊斯兰数学中就已经较清楚、广泛(在多种著作中发现)地使用了数学归纳法的归纳推理.

中世纪前期的欧洲被称为文化史的“黑暗时代”,文化教育名存实亡,古老学问濒临绝迹,技艺艺术逐渐遗忘,社会秩序严重被毁,暴力宗教肆意顺行.中世纪后期情况有所改观,十字军东征带回了东方文化,并从阿拉伯重新捡回了古希腊文化,此时欧洲数学自身的发展仍然及其缓慢,更多的是传播印度、伊斯兰等东方的数学知识,就连意大利数学家L?错误！未找到引用源。斐波那契(Lenardo F bonacci,约1170～1250,也称比萨的莱昂那多),写于1202年的名作《算盘书》也主要介绍、引证了许多印度、伊斯兰等国的数学知识和数学问题,包括阿拉伯数字的写法、用法,四则运算、方程解法等,这本书作为教材在欧洲各国几乎使用了近200年,可见数学知识更新之缓慢.德国数学家和数学史家汉克尔(H?错误！未找到引用源。Hankel,1839～1873)风趣地形容这一现象,“人们惊奇地发现,莱昂那多给予欧洲的那一磅钱,在300年间竟丝毫没有生出什么利息”.J?错误！未找到引用源。H?错误！未找到引用源。伊夫斯则称,十四世纪欧洲相对地是数学上的不毛之地,这不仅因为十四世纪下半叶黑死病扫荡了欧洲三分之一以上的人口,也因为这是一个政治、经济动荡,战争不断的世纪,这种影响一直延续到文艺复兴.如此状况,莱维?错误！未找到引用源。本?错误！未找到引用源。热尔松的贡献也算是给中世纪欧洲数学增添了一份光彩.

中世纪的伊斯兰则与欧洲大不相同,其商业繁荣,文化活跃,占希腊、印度的数学知识几乎全部传播到那里,被吸收消化并形成自己独特的风格,他们将希腊数学中几何证明的思想,转移到代数学研究中,希望能够证明代数规则的合理性.伊斯兰的代数中充满了证明的思想,很多计算问题都被他们扩展为可以对一般情形也成立的形式,归纳推理思想(这里的归纳推理指的是数学中的递推,而非普通逻辑中的归纳法的推理)就是在这样一种氛围中被逐步凝炼.

2 数学归纳法的原理

自然科学中的“经验归纳法”,是从某一现象的一系列特定的观察出发,归纳出支配该现象所有情况的一般规律,而数学归纳法则是迥然不同的另种手段,它用来证实

2

晋中学院XX学院20XX届本科生毕业论文

有关无限序列（第一个,第二个,第三个,等等,没有一个情况例外）的数学定理的正确性.

数学归纳法原理:假设我们希望证明一系列无限个数学命题A1,A2,A3,它们合在一起便构成一般的命题A.如果

a）通过某种数学论证可以证明,对于任一整数r,如果命题Ar错误！未找到引用源。已知为真,则命题Ar?1随之亦真;

b）第一个命题A1错误！未找到引用源。已知为真,那么序列中所有命题必都为真,从而A得证.

数学归纳法的原理是奠基在下属事实的基础上:在任一整数r之后接着便有下一个r?1,从而从整数1 出发,通过有限多次这种步骤,便能达到任意选定的整数n.

推广后的数学归纳法原理:假设给定一系列命题As,As?1,As?2错误！未找到引用源。,?,其中s是某正整数,如果

a）对于每个r?s,Ar?1错误！未找到引用源。的正确性可以从Ar的正确性导出, b）As已知为真

则所有命题As,As?1,As?2错误！未找到引用源。,?均为真;换句话说,对于所有的

n?s,An为真.

我们再次强调指出,在自然科学中,数学归纳法原理与经验归纳法是完全不同的,一般的定律如果被证实了任意有限次,那么不论次数多么多,甚至至今尚未发现例外,都不能说该定律在严格的数学意义下被证明了,这种定律只能算作十分合理的假设,它容易为未来的经验结果所修正.在数学中,一条定律或一个定理所谓被证明了,指它是从若干作为真理接受的假设出发而得到的逻辑推论.人们考察一个定理,如果它在许多实例中是正确的,那么就可猜想定理在普遍意义下将是真的;然后人们尝试用数学归纳法以证明之.如果尝试成功,定理被证明为真;如果尝试失败,则定理的真伪未定,有待以后用其他方法予以证明或者推翻.

因此在应用数学归纳法原理是要牢记a）和b）必须真正的满足.

3 数学归纳法

3

晋中学院XX学院20XX届本科生毕业论文

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都成立.

与第一数学归纳法相比,第二数学归纳法把它的归纳假设加强了. 3.2 两种归纳法之间的关系

定理3.2.1 第一数学归纳法和第二数学归纳法等价.

证明 假设性质P(n)在n?1时成立,于是化为证明:“由P(k)成立,则可以推出的充分必要条件为“由P(n)（其中n?k）成立,可以推出P(k?1)成立”. P(k?1)成立”

必要性:由已知“由P(k)成立,则可以推出P(k?1)成立”,假设n?k时P(n)成立,特别P(k)成立,所以P(k?1)成立.得证.

充分性:（反证法证明）由已知n?k时P(n)成立,可以推出P(k?1)成立,对“由

P(k)成立,则可以推出P(k?1)成立”取反，于是,由P(k0)成立推不出P(k0?1)成立

的所有自然数错误！未找到引用源。构成一非空子集,记m为该子集的最小自然数.所以,对任一自然数n,只要n?m,那么由P(n)成立可以推出P(k?1)成立.特别,由

P(1)成立可知P(2)成立,?,由P(m?1)成立可知P(m).已知P(1)成立,因此P(1)、P(2)、?、P(m)都成立,然而由此可知P(m?1)成立,所以从P(m)成立推出了P(m?1)成立;另一方面,由m的选取可知,由P(m)成立推不出P(m?1)成立,这就导出矛盾,得证.

4

晋中学院XX学院20XX届本科生毕业论文

4 数学归纳法的理论基础及其证明 4.1 第一数学归纳法的理论基础及证明

第一数学归纳法的理论基础为自然数的序数理论,是由意大利数学家Peano 于1889 年在他的著作《 算数原理新方法》 中提出.理论用公理化的方法从顺序的角度揭示了自然数的意义,即我们所说的自然数1、2、3??理解为第1 个、 第2 个、 第3 个??下面用定义的方式给出这个公理的内容.

定义4.1.1 一个非空集合N的元素叫做自然数,如果N的元素之间有一个基本关系“后继”( 用符号′错误！未找到引用源。来表示),并满足下列公理:

(1)1?N,对???N,???1

(2)对任何??N有唯一的后继元素错误！未找到引用源。

(3)1以外的任何元素只能是一个元素的后继元素,即1不排在任何自然数后面 (4)归纳公理:若M?N且

①1?M

②??M????M则M?N(N自然数集)

定义中的一组公理叫Peano 公理.它完整地刻画了自然数列.而其中的公理(4)即归纳公理可推出第一数学归纳法.

第一数学归纳法:设P(n)是一个与自然数有关的命题,如果:P(1)成立,假设P(k)成立,则P(k?1)成立,那么对任意自然数P(n)都成立.

证明 设M是由满足P(n)的自然数组成的集合则M?N ∵P(1)成立,则1?M 又∵假设P(k)成立,则P(k?1)成立

即k?M?k?1?M,即k?M?k??M.由归纳公理M?N,M为自然数集,即P(n)对任意自然数都成立.

从上述证明过程可以看出第一数学归纳法的理论依据为归纳公理. 4.2 第二数学归纳法的理论基础及证明

第二数学归纳法也属于数学归纳法.它的理论依据为最小数原理,而最小数原理实际上也是归纳公理得出的.

5

晋中学院XX学院20XX届本科生毕业论文

最小数原理:自然数集的任一非空子集中必有一个最小数.

证明 设A为N的任一非空子集,假设n?N且n?1,则n必为某一自然数m的后继.

∴n?m??m?1?1 ∴自然数集N有最小数1 ∴ 当1?A,A有最小数1

当1?A时,假设A没有最小数,构造集合T?{x|x?N且对?a?A,x?a},则

1?T.

假设n?T,若n?1?A,则n?1为A中的最小数,与假设矛盾. ∴n?1?T

那么1?T,n?T时n?1?T

由归纳公理T?N则A?错误！未找到引用源。与A为非空集矛盾 ∴N的任一非空子集中必有一个最小数. 以上是用归纳公理对最小数原理作证明. 下面用最小数原理对第二数学归纳法做一个证明.

第二数学归纳法:设P(n)是一个与自然数有关的命题,若下列两个条件成立 ⑴P(1)成立

⑵假设P(n)对于所有满足l?k成立,则P(k)成立 那么P(n)对所有自然数成立

证明 设M为满足P(n)成立的所有自然数n的集合,设T?N?M,假设T?错误！未找到引用源。,根据最小数原理T有最小数t0.由条件⑴P(1)成立,则1?M.

∴t0?1

∴1、2、t0?1?M 又由条件⑵t0?T矛盾 ∴T?错误！未找到引用源。 ∴M?N 6

晋中学院XX学院20XX届本科生毕业论文

∴P(n)对任意自然数成立.得证.

5 数学归纳法在各门学科中的简单应用 5.1 数学归纳法在初等数学中的应用

数学归纳法在归纳猜想问题及不等式证明问题中等都有着广泛的应用.

1111???2例1 对任意自然数n,求??的和.

315354n?1证明 设

1111?????2 315354n?1的和为Sn, 则

11111111???2?????=. Sn=??315354n?14?12?14?22?14?32?14?n2?1先对n?1,2,3,4,5分别进行计算,再寻找其中的规律. 显然

12345S1?,S2?,S3?,S4?,S5?.

357911S的下标就是项数,观察S1~S5,可以看出他们的分子都与其项数相同.把分母变形,

则有

S1?12345,S2?,S3?,S4?,S5?. 1?22?33?44?55?6或者再写成

12345,S2?,S3?,S4?,S5?.

2?1?12?2?12?3?12?4?12?5?1n66?于是我们就猜想:Sn?.再观察n =6的情形,有S6?,又符合

2n?1132?6?177?我们的猜想.再观察一下n =7,则有S7?.此时我们对于上面的猜想就更152?7?1S1?有信心了.

然而至今采用的还是经验归纳法,要确定

n是Sn的求和公式,还要经过严格2n?1的证明.如何证明它呢?这恰好是一个与自然数有关的命题,所以我们不妨试一下数学归纳法.

7

晋中学院XX学院20XX届本科生毕业论文

设

Sn?n 2n?1只要能证得

Sn?1?n?1n?1 ?2?(n?1)?12n?3即可.

事实上

Sn?1?Sn?1n1n1????4(n?1)2?12?n?122?(n?1)2?12?n?1(2n?2?1)(2n?2?1)n(2n?3)1(2n?1)(n?1)n?1????(2n?1)(2n?3)(2n?1)(2n?3)(2n?1)(2n?3)2n?3证毕.

5.2 数学归纳法在高等代数中的应用

数学归纳法在高等代数中的应用也很突出,这主要是由高等代数内容体系所决定,其中许多证明及行列式的计算等,都要用到数学归纳法.

例2 设

?2a1??2?a2a1??2??a2a1A???

??????a22a1???2a2a????是n阶矩阵,证明行列式

A?(n?1)an.

证明 记

2a1a22aDn?A?a212a1???a22a1a22an?n,

8

晋中学院XX学院20XX届本科生毕业论文

下面用数学归纳法证明:

当n?1时,D1?2a,命题Dn?(n?1)an正确. 当n?2时, D2?2aa212a?3a2,命题Dn?(n?1)an正确.

当n?k时,命题Dn?(n?1)an正确,对Dk按第一列展开得

2a1a22aDk?2aa212a1???a21a2?a2(?1)2?102a1???a22a1a22ak?1

2a1a22ak?1?2aDk?1?a2Dk?2

按归纳假设

Dk?1?kak?1,Dk?2?(k?1)ak?2,

从而

Dk?2a(kak?1)?a2(k?1)ak?2?(k?1)ak,

所以?n,命题

A?(n?1)an正确.

例3 计算行列式:

1Dn?cos?1cos2?1?cos(n?1)?11cos?2cos2?2?cos(n?1)?21cos?3cos2?3?cos(n?1)?3?????1cos?ncos2?n?cos(n?1)?n

分析 这个行列式如果直接计算很困难,也很难发现什么规律.但是,如果先从特殊情况入手就容易发现规律. 当n?3时,

1D3?cos?11cos?21cos?3?1cos?11cos?21cos?3

cos2?1cos2?2cos2?32cos2?1?12cos2?2?12cos2?3?19

晋中学院XX学院20XX届本科生毕业论文

1?cos?1?21cos?2?cos?i)

111cos?21cos?3

cos?3?2cos?12cos2?12cos2?22cos2?31?i?j?3cos2?1cos2?2cos2?3?(cos?j这里利用了范德蒙行列式的计算公式. 当n?4时,

1cos?1cos2?1cos3?11cos?2cos2?2cos3?21cos?3cos2?3cos3?31cos?4cos2?4cos3?41cos?22cos?2?14cos3?2?3cos?21cos?32cos2?34cos3?31cos?42cos2?44cos3?42D4?

?1cos?12cos?1?14cos3?1?3cos?11cos?12cos2?14cos3?11?i?j?421cos?32cos?3?14cos3?3?3cos?321cos?42cos?4?14cos3?4?3cos?42

?1cos?22cos2?24cos3?2j

?21?2?(cos??cos?i)

由此可以猜想:

Dn?21?2?3??(n?2)1?i?j?n?(cos?j?cos?i)?2(n?2)(n?1)21?i?j?n?(cos?j?cos?i)

下面用数学归纳法证明.

证明 当n?3时,已证,原等式成立.

假设3?n?k(k?3)时,原不等式成立,下证n?k?1时也成立.

1cos?1Dn?cos2?1?cosk?11cos?2cos2?2?cosk?21cos?3cos2?3?cosk?3?????1cos?k?1cos2?k?1 ?cosk?k?110

晋中学院XX学院20XX届本科生毕业论文

将行列式的第k?1行加到第k?1行,再将第k行的?2cos?1加到第k?1行.然后将第

k?2行加到第k行, 将第k?1行的?2cos?1加到第k行,依此类推

10Dk?1?0?01cos?2?cos?12cos?2(cos?2?cos?1)?2cos(k?1)?2(cos?2?cos?1)?????1cos?k?1?cos?12cos?k?1(cos?k?1?cos?1)?2cos(k?1)?k?1(cos?k?1?cos?1)1cos?2 ?cos(k?1)?2

?(cos?2?cos?1)(cos?3?cos?1)?(cos?k?1?cos?1)2k?11???1cos?k?1?cos(k?1)?k?1

cos?2?cos(k?1)?2,

由假设得:

1cos?2?cos(k?1)?2?2(k?2)(k?1)21cos?3?cos(k?1)?3j???1cos?k?1?cos(k?1)?k?1

2?i?j?k?1?(cos??cos?i)

从而有:

Dk?1?(cos?2?cos?1)(cos?3?cos?1)?(cos?k?1?cos?1)2k(k?1)2k?12(k?2)(k?1)22?i?j?k?1?(cos?j?cos?i)?21?i?j?k?1?(cos?j?cos?i)

所以猜想成立.

11

晋中学院XX学院20XX届本科生毕业论文

5.3 数学归纳法在离散数学方面的应用

离散数学以离散问题为研究对象其中很多的结论均与自然数有关,并可以运用数学归纳法来证明离散数学中的某些结论,如有关集合中关系及性质、树及其性质等,这样既降低了证明过程的复杂性,又使推理过程更加严密清晰.

例4 已知设d1,d2,?,dn是n个正整数,n?2,已知?di?2n?2,证明存在结

i?1n点度数分别为d1,d2,?,dn的一棵树.

证明 对结点n归纳证明,可构造满足条件的树T.

(1) n?2时,由d1?d2?4?2?2,而d1,d2?1,所以d1?d2?1,于是存在T2为满足条件的树.

(2)假设n?k时结论成立,即存在结点度数分别为d1,d2,?,dk的一棵树T1,要证n?k?1时,结论也成立.

由d1,d2,?,dk, dk?1均为正整数, ?di?2(k?1)?2?2k知这k?1个数中至

i?1k?1少有二个为1,否则?di?2k?1,与条件矛盾.

i?1k?1不妨设dk?1?1,于是?di?2k?1,这样d1,d2,?,dk中至少有一个大于等于2,

i?1k否则?di?k矛盾.

i?1k不妨设dk?2,于是dk?1?1,?di?(dk?1)??di?1?2k?2,

i?1i?1k?1k考虑d1,d2,?,dk?1, dk?1这个正整数,由归纳假设知,存在结点度数分别是

d1,d2,?,dk?1, dk?1的一棵树T1,在T中从度为dk?1的结点vk引出一条边,另一端点记为vk?1,这样得一棵新树T,在T中deg(vk)?dk,deg(vk?1)?dk?1?1.

于是?deg(vi)??di?2(k?1)?2,因此, T即为所求的一棵树.

ii?1k?1k?15.4 数学归纳法在高等数学中的应用

12

晋中学院XX学院20XX届本科生毕业论文

例5 证明不等式1?12?13?L?1n?2n(n?N).

证明 (1)当n?1时,左边?1,右边?2,左边?右边. ∴不等式成立.

(2)假设当n?k时,不等式成立,即

1?12?13?L?1k?2k,

当n?k?1时,则

1?12?1k?113?L?1k?11?k?2k?11?k

(现在关键证明2k??2k?1)

2k?

1?k?1k?(k?1)?1k?11k?1?2k?1?2k?k?1?1k?1?2k?1

?2k?1?2k?1?2k?1?0∴2k??2k?1,即当n?k?1时,原不等式成立.

综合(1)(2)对于任意自然数n命题成立.

例6 求证

cosa?cos2a?cos2aLcos22n?1sin2naa?n(sina?0)

2sina证明 (1)当n?1时,左边

sin2a2sinacosa??cosa, 2sina2sina所以当n?1时命题成立.

(2)假设当n?k(k?1)时命题成立,即:

cosa?cos2a?cos2aLcos22k?1sin2kaa?k

2sina将此试的两边同乘以cos2ka得:

13

晋中学院XX学院20XX届本科生毕业论文

cosa?cos2a?cos2aLcos22k?1sin2kaa?cos2a?k?cos2ka

2sinak2sin2ka?cos2kasin2k?1a??sina kk?12?2sina2所以当n?k?1时命题成立.综合(1)(2)对于任意自然数n命题成立. 5.5 数学归纳法在图论中的应用

例7 大于7公斤整公斤的重量都可以仅用一些3公斤和5公斤两种砝码来称量. 证明 只需证明对任意的自然数n?8,存在二分图G?n?,其X顶子集有n个顶点,每顶皆一次,Y顶子集中的顶是3次或5次的.

下面用数学归纳法证明之. 当n?8时,结论显然成立,见下图:

X x1 x2 x3 x4 x5 x6 x7 x8 Y y1 y2

假设对于G?k?,结论一成立,k?8.以下证明对G?k?1?,结论仍成立.为此,在G?k?的X顶子集中添加一项xk?1;由归纳法假设,在G?k?的Y中顶是3次或5次的,分以下情形讨论:

(i)若Y中皆3次项,取y1,y2,y3,将其重合成一项y123,再于y123与xk?1之间连一条边,最后把y123劈开成两个5次项,则得满足要求的G?k?1?.

14

晋中学院XX学院20XX届本科生毕业论文

(ii)若Y中有5次项,设d(yi)?5,在yi与xk?1之间连一边,再把yi劈开成两个3次项,则得满足要求的二分图G?k?1?.

证毕.

5.6 数学归纳法在概率论方面的应用

在概率问题中常会遇到一些与实验次数无关的重要结论,这些结论在使用数学归纳法来证明时,常常需要配合使用全概率公式,从而使概率论中的数学归纳法具有自己的特色.

例8 设有n个罐子,在每一个罐子中各有m个白球与k个黑球,从第一个罐子中任取一球放入第二个罐子中,并依此类推,求从最后一个罐子中取出一个白球的概率.

解析 先探索规律,设n?2

令H1?“从第一个罐子中取出一个球,是白球”

H2?“从第二个罐子中取出一个球,是白球” 显然P(H1)?m,所求概率 m?kP(H2)?P(H1)P(H2|H1)+P(H1)P(H2|H1)

?mm?1kmm??

m?km?k?1m?km?k?1m?k这恰与n?1时的结论是一样的,于是可以预见,不管n是什么自然数,所求的概率都应是

m,则当n?t?1时,有 m?kP(Ht?1)?P(Ht)P(Ht?1|Ht)+P(Ht)P(Ht?1|Ht)

?于是,结论P(Hn)?

6 结束语

毕业设计,也许是我大学生涯交上的最后一个作业了.想籍次机会感谢四年以来给我帮助的所有老师、同学,你们的友谊是我人生的财富,是我生命中不可或缺的一部分.我的毕业论文指导老师孙彩云老师,虽然我们是在开始毕设时才认识,但她却能以一位长辈的风范来容谅我的无知和冲动,给我不厌其烦的指导.在此,特向她道声谢

15

mm?1kmm??.

m?km?k?1m?km?k?1m?km对所有自然数都成立. m?k 晋中学院XX学院20XX届本科生毕业论文

谢.

大学生活即将匆匆忙忙地过去,但我却能无悔地说:“我曾经来过.”大学四年,但它给我的影响却不能用时间来衡量,这四年以来,经历过的所有事,所有人,都将是我以后生活回味的一部分,是我为人处事的指南针.就要离开学校,走上工作的岗位了,这是我人生历程的又一个起点,在这里祝福大学里跟我风雨同舟的朋友们,一路走好,未来总会是绚烂缤纷.

参考文献

[1] 冯进.数学归纳法的发展历程[N].常熟理工学院学报,2008,22(8):21～22.

[2] 刘艳.数学归纳法的原理及应用[J].山西经济管理干部学院学报,2011,19(3):135～136. [3] 程克玲.数学归纳法及其应用[J].赤峰学院学报,2011,27(3):22～23. [4] 王仁发,代数与解析几何[M].长春:东北师范大学出版社,1999. [5] 陈丽,刘晓霞.离散数学[M],北京:高等教育出版社,2002. [5] 王树禾.图论[M].北京:科学出版社,2009.

[6] 刘西垣,李永乐等.2012年李永乐·李正元考研数学复习全书[M].北京:国家行政学院出版

社,2009.

16

本文来源：https://www.bwwdw.com/article/roor.html