浅谈数学归纳法及其应用

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

浅谈数学归纳法及其应用
学生姓名:XXX(XXX 班) 指导老师:XXX



要:数学归纳法是数学中最基本也是最重要的证明方法之一 ,在数学各个分支里

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

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

On the Mathematical Induction and its Application

Student: X Instructor: X

XX 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 2 3



数学归纳法的思想渊源?????????????????1 数学归纳法的原理???????????????????2 数学归纳法??????????????????????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 届本科生毕业论文

最小数原理:自然数集的任一非空子集中必有一个最小数. 证明 后继. ∴ n ? m? ? m ? 1 ? 1 ∴自然数集 N 有最小数 1 ∴ 当 1 ? A , A 有最小数 1 当 1 ? A 时, 假设 A 没有最小数 , 构造集合 T ? { x | x ? N 且对 ?a ? A , x ? a }, 则
1? T .

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

假设 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 有最小数 t 0 .由条件⑴ P(1) 成立,则 1 ? M . ∴ t0 ? 1 ∴1 、 2 、 t0 ? 1? M 又由条件⑵ t 0 ? T 矛盾 ∴ T ? 错误!未找到引用源。 ∴M ? N

6

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

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

5 数学归纳法在各门学科中的简单应用 5.1 数学归纳法在初等数学中的应用 数学归纳法在归纳猜想问题及不等式证明问题中等都有着广泛的应用. 例1
1 1 1 1 ??? 2 对任意自然数 n ,求 ? ? 的和. 3 15 35 4n ? 1

证明


1 1 1 1 ? ? ??? 2 3 15 35 4n ? 1

的和为 S n , 则
1 1 1 1 1 1 1 1 ??? 2 ? ? ??? = . Sn = ? ? 2 2 2 3 15 35 4n ? 1 4 ? 1 ? 1 4 ? 2 ? 1 4 ? 3 ? 1 4 ? n2 ?1

先对 n ? 1,2,3,4,5 分别进行计算,再寻找其中的规律. 显然
1 2 3 4 5 S1 ? , S 2 ? , S 3 ? , S 4 ? , S 5 ? . 3 5 7 9 11
S 的下标就是项数,观察 S1 ~ S5 ,可以看出他们的分子都与其项数相同.把分母变形,

则有
S1 ? 1 2 3 4 5 , S2 ? , S3 ? , S4 ? , S5 ? . 1? 2 2?3 3? 4 4?5 5?6

或者再写成
1 2 3 4 5 , S2 ? , S3 ? , S4 ? , S5 ? . 2 ?1 ? 1 2? 2 ?1 2? 3 ?1 2? 4 ?1 2?5 ?1 n 6 6 ? 于是我们就猜想: S n ? .再观察 n =6 的情形,有 S 6 ? ,又符合 2n ? 1 13 2 ? 6 ? 1 7 7 ? 我们的猜想.再观察一下 n =7,则有 S 7 ? .此时我们对于上面的猜想就更 15 2 ? 7 ? 1 S1 ?

有信心了. 然而至今采用的还是经验归纳法,要确定
n 是 S n 的求和公式,还要经过严格 2n ? 1

的证明.如何证明它呢?这恰好是一个与自然数有关的命题,所以我们不妨试一下数学 归纳法.

7

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


Sn ? n 2n ? 1

只要能证得
S n ?1 ? n ?1 n ?1 ? 2 ? (n ? 1) ? 1 2n ? 3

即可. 事实上

S n ?1 ? S n ?

1 n 1 n 1 ? ? 2 ? ? 2 2 4(n ? 1) ? 1 2 ? n ? 1 2 ? (n ? 1) ? 1 2 ? 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 设

? 2a 1 ? ? 2 ? ? a 2a 1 ? ? ? a 2 2a 1 A?? ? ? ? ? ? ? 2 ? a 2a 1 ? ? ? a 2 2a ? ? ? ?
是 n 阶矩阵,证明行列式

A ? (n ? 1)a n .
证明 记

2a 1 a 2 2a Dn ? A ? a
2

1 2a 1 ? ? ? a2 2a 1 a 2 2a n?n
,

8

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

下面用数学归纳法证明: 当 n ? 1 时, D1 ? 2a ,命题 Dn ? (n ? 1)a n 正确. 当 n ? 2 时, D2 ?

2a a
2

1 2a

? 3a 2 ,命题 Dn ? (n ? 1)a n 正确.

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

2a 1 a 2 2a Dk ? 2 a a2

1 2a 1 ? ? ? a
2

1 a2 ? a 2 (?1) 2?1

0 2a 1 ? ? ? a2 2a 1 a 2 2a k ?1

2a 1 a 2 2a k ?1

? 2aDk ?1 ? a 2 Dk ?2
按归纳假设

Dk ?1 ? ka k ?1 , Dk ?2 ? (k ? 1)a k ?2 ,
从而

Dk ? 2a(kak ?1 ) ? a 2 (k ? 1)a k ?2 ? (k ? 1)a k ,
所以 ?n ,命题 例3

A ? (n ? 1)a n 正确.

计算行列式:
1 1 cos? 2 cos 2? 2 ? cos(n ? 1)? 2 1 cos? 3 cos 2? 3 ? cos(n ? 1)? 3 ? ? ? ? ? 1 cos? n cos 2? n ? cos(n ? 1)? n cos?1 cos 2?1 ?

Dn ?

cos(n ? 1)?1

分析

这个行列式如果直接计算很困难,也很难发现什么规律.但是,如果先从特

殊情况入手就容易发现规律. 当 n ? 3 时,

1 D3 ? cos?1

1 cos? 2

1 cos? 3 ?

1 cos?1
2

1 cos? 2
2

1 cos? 3

cos 2?1 cos 2? 2 cos 2? 3

2 cos ?1 ? 1 2 cos ? 2 ? 1 2 cos2 ? 3 ? 1

9

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

1 ? cos?1
?2

1 cos? 2
? cos?i )

1

1

1 cos? 2

1 cos? 3

cos? 3 ? 2 cos?1

2 cos2 ?1 2 cos2 ? 2 2 cos2 ? 3
1?i ? j ?3

cos2 ?1 cos2 ? 2 cos2 ? 3

? (cos?

j

这里利用了范德蒙行列式的计算公式. 当 n ? 4 时,
1 cos?1 cos 2?1 cos3?1 1 cos? 2 cos 2? 2 cos3? 2 1 cos? 3 cos 2? 3 cos3? 3 1 cos? 4 cos 2? 4 cos3? 4 1 cos? 2 2 cos2 ? 2 ? 1 4 cos3 ? 2 ? 3 cos? 2 1 cos? 3 2 cos2 ? 3 4 cos3 ? 3 1 cos? 4 2 cos2 ? 4 4 cos3 ? 4 1 cos? 3 2 cos2 ? 3 ? 1 4 cos3 ? 3 ? 3 cos? 3 1 cos? 4 2 cos2 ? 4 ? 1 4 cos3 ? 4 ? 3 cos? 4

D4 ?

?

1 cos?1 2 cos2 ?1 ? 1 4 cos3 ?1 ? 3 cos?1 1 cos?1 2 cos2 ?1 4 cos3 ?1
1?i ? j ?4

?

1 cos? 2 2 cos2 ? 2 4 cos3 ? 2
j

? 21?2

?(cos?

? cos? i )

由此可以猜想:
Dn ? 2
1? 2 ? 3??( n ? 2 )

1?i ? j ? n

? (cos ?

j

? cos ? i ) ? 2

( n ? 2 )( n ?1) 2

1?i ? j ? n

? (cos ?

j

? cos ? i )

下面用数学归纳法证明. 证明 当 n ? 3 时,已证,原等式成立.

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

10

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

将行列式的第 k ? 1 行加到第 k ? 1 行,再将第 k 行的 ? 2 cos?1 加到第 k ? 1 行.然后将第
k ? 2 行加到第 k 行, 将第 k ? 1 行的 ? 2 cos?1 加到第 k 行,依此类推
1 0 Dk ?1 ? 0 ? 0 1 cos? 2 ? cos? 1 2 cos? 2 (cos? 2 ? cos? 1 ) ? 2 cos(k ? 1)? 2 (cos? 2 ? cos? 1 )

? ? ? ? ?

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

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

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

? ? ?

1 cos? k ?1 ? cos(k ? 1)? k ?1

,

由假设得:
1 cos? 2 ? cos(k ? 1)? 2
?2
( k ? 2 )( k ?1) 2

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

? ? ?

1 cos? 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 )2 k ?1 2
k ( k ?1) 2
( k ? 2 )( k ?1) 2

2 ?i ? j ? k ?1

? (cos ?

j

? cos ? i )

?2

1?i ? j ? k ?1

? (cos ?

j

? cos ? i )

所以猜想成立.
11

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

5.3 数学归纳法在离散数学方面的应用 离散数学以离散问题为研究对象其中很多的结论均与自然数有关,并可以运用数 学归纳法来证明离散数学中的某些结论 ,如有关集合中关系及性质、树及其性质等 , 这样既降低了证明过程的复杂性,又使推理过程更加严密清晰. 例4 已知设 d1 , d 2 ,?, d n 是 n 个正整数, n ? 2 ,已知 ? d i ? 2n ? 2 ,证明存在结
i ?1 n

点度数分别为 d1 , d 2 ,?, d n 的一棵树. 证明 对结点 n 归纳证明,可构造满足条件的树 T .

(1) n ? 2 时,由 d1 ? d 2 ? 4 ? 2 ? 2 ,而 d1 , d 2 ? 1 ,所以 d1 ? d 2 ? 1 ,于是存在 T2 为 满足条件的树. (2)假设 n ? k 时结论成立,即存在结点度数分别为 d1 , d 2 ,?, d k 的一棵树 T1 ,要 证 n ? k ? 1 时,结论也成立. 由 d1 , d 2 , ? , d k , d k ?1 均为正整数,
k ?1 i ?1

?d
i ?1

k ?1

i

? 2(k ? 1) ? 2 ? 2k 知这 k ? 1 个数中至

少有二个为 1,否则 ? d i ? 2k ? 1 ,与条件矛盾. 不妨设 d k ?1 ? 1 ,于是 ? d i ? 2k ? 1 ,这样 d1 , d 2 ,?, d k 中至少有一个大于等于 2,
i ?1 k

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

k

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

k ?1

k

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

d1 , d 2 ,?, d k ?1 , d k ? 1 的一棵树 T1 ,在 T 中从度为 d k ? 1 的结点 vk 引出一条边,另一
端点记为 v k ?1 ,这样得一棵新树 T ,在 T 中 deg(vk ) ? d k , deg(vk ?1 ) ? d k ?1 ? 1 . 于是 ? deg(vi ) ? ? d i ? 2(k ? 1) ? 2 ,因此, T 即为所求的一棵树.
i i ?1 k ?1 k ?1

5.4 数学归纳法在高等数学中的应用
12

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

例5 证明

证明不等式 1 ?

1 2

?

1 3

?L?

1 n

? 2 n (n ? N ) .

(1)当 n ? 1 时,左边 ? 1 ,右边 ? 2 ,左边 ? 右边.

∴不等式成立. (2)假设当 n ? k 时,不等式成立,即
1? 1 2 ? 1 3 ?L? 1 k ?2 k,

当 n ? k ? 1 时,则
1? 1 2 ? 1 k ?1 1 3 ?L? 1 k ? 1 1? k ?2 k ? 1 1? k

(现在关键证明 2 k ?

? 2 k ?1 )

2 k? ?

1

k ?1 k ? (k ? 1) ? 1 k ?1
1 k ?1

? 2 k ?1 ?

2 k ? k ?1 ?1 k ?1

? 2 k ?1

? 2 k ?1 ? 2 k ?1 ? 2 k ?1 ? 0

∴2 k ?

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

综合(1)(2)对于任意自然数 n 命题成立. 例6 求证
cosa ? cos2a ? cos2 2 aL cos2 n?1 a ? sin 2 n a (sin a ? 0) 2 n sin a

证明

(1)当 n ? 1 时,左边
sin 2a 2 sin a cos a ? ? cos a , 2 sin a 2 sin a

所以当 n ? 1 时命题成立. (2)假设当 n ? k (k ? 1) 时命题成立,即:
cosa ? cos2a ? cos2 2 aL cos2 k ?1 a ? sin 2 k a 2 k sin a

将此试的两边同乘以 cos2 k a 得:

13

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

cosa ? cos 2a ? cos2 2 aL cos 2 k ?1 a ? cos2 k a ?

sin 2 k a ? cos2 k a k 2 sin a 2 sin 2k a ? cos 2k a sin 2k ?1 a ? sin a 2 ? 2k sin a 2k ?1

?

所以当 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 , y 2 , 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

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

H 2 ? “从第二个罐子中取出一个球,是白球”
显然 P ( H 1 ) ?
m ,所求概率 m?k

P( H 2 ) ? P( H1 ) P( H 2 | H1 ) + P( H1 ) P( H 2 | H1 )
? m m ?1 k m m ? ? m ? k m ? k ?1 m ? k m ? k ?1 m ? k

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

P( H t ?1 ) ? P( H t ) P( H t ?1 | H t ) + P(H t )P(H t ?1 | H t )
? m m ?1 k m m ? ? . m ? k m ? k ?1 m ? k m ? k ?1 m ? k

于是,结论 P ( H n ) ?

m 对所有自然数都成立. m?k

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

晋中学院 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


相关文档

浅谈数学归纳法的应用
浅谈数学归纳法的两个步骤及其应用
浅谈数学归纳法及其在中学数学中的应用2
浅谈数学归纳法的应用技巧
浅谈数学归纳法的应用数学毕业论文
浅议数学归纳法的应用
浅谈数学归纳法的认识及应用
浅析数学归纳法原理及应用举例
数学论文 浅谈数学归纳法的应用
浅议数学归纳法在高中数学中的应用
电脑版