(完整版)浅谈数学归纳法及其应用,推荐文档

1、晋中学院 xx 学院 20xx 届本科生毕业论文浅谈数学归纳法及其应用学生姓名:xxx（xxx 班） 指导老师:xxx摘要:数学归纳法是数学中最基本也是最重要的证明方法之一,在数学各个分支里都有广泛应用,利用数学归纳法可以解决比较复杂的问题.本文从数学归纳法的整体结构出发,对数学归纳法的思想渊源、基本原理及常见形式进行了分析总结,介绍了数学归纳法在初等数学、高等数学、离散数学、概率论、图论等学科中的应用.关键词:数学归纳法;渊源;原理;表现形式;理论基础及其证明;应用on the mathematical induction and its applicationstudent: xxx in

2、structor: xxxabstract: 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.

3、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 inductio

4、n;origin;theory;manifestations;theoretical foundation and its proof;application目 录1 数学归纳法的思想渊源12 数学归纳法的原理23 数学归纳法33.1 数学归纳法的具体表现形式33.2 两种归纳法之间的关系44 数学归纳法的理论基础及其证明44.1 第一数学归纳法的理论基础及其证明44.2 第二数学归纳法的理论基础及其证明55 数学归纳法在各门学科中的简单应用65.1 数学归纳法在初等数学中的应用65.2 数学归纳法在高等代数中的应用85.3 数学归纳法在离散数学方面的应用115.4 数学归纳法在高等数学中的应

5、用125.5 数学归纳法在图论中的应用145.6 数学归纳法在概率论方面的应用146 结束语15参考文献16晋中学院 xx 学院 20xx 届本科生毕业论文1 数学归纳法思想的渊源追根溯源数学归纳法可以在印度和古希腊时代的著作中找到丝缕痕迹,例如,印度婆什迦罗（bashkiria 1114约 1185）的“循环方法”和欧几里得素数无限的证明中都可以找到这种踪迹.欧几里得几何原本第九卷命题 20 为:质数比任何指定数目都要多（注:质数也称为素数）,即:素数无穷.欧几里得对这个命题的证法是经典的.他假定素数是有限的,不妨设这有限的n 个素数为 p1 , p2 ,l, pn .然后作自然数p1 ,

6、p2 ,l, pn+1 并证明还存在新的素数,从而得到矛盾.因为若所作的数是素数,则它比全部给出的n 个素数都要大,因此是一个新的素数,这与假设有n 个素数矛盾;又若它不是素数,它必能被一素数整除,但它被已知全部的n 个素数 p1, p2 ,l, pn .除都有余数1,故整除 p1, p2 ,l, pn+1 的素数必定是这n 个素数以外的新的素数,从而又与假设有n 个素数的条件矛盾.欧几里得素数无穷命题即是说,素数的个数与自然数的个数一样多.上述证明可以这样“翻译”,首先,至少有一个素数存在,因为 2 就是素数,这一点在欧几里得的证明中没有指明;此外,上面欧几里得的证明表明,假如有n 个素数,

7、那么就必定有n + 1 个素数存在.也就是按现代数学归纳法的要求,证明了从n 到n + 1 的递推关系,即完成了数学归纳法证明的关键性一步.但欧几里得没有使用任何明显的术语与现在的推理格式,因此,我们只能认为它蕴涵了现代数学归纳法的痕迹.现代形式的数学归纳法被很多人认为是法国数学家、物理学家和哲学家帕斯卡(bpascal,16231662)发现的.例如,德国数学家和数学史家 mb康托尔(mbcantor,18291920)在他最重要的著数学史演讲卷 2 第 749 页中就这样误定,后来他在有关的杂志中作了纠正,他说,华卡(gvacca?)先生告诉我,意大利的莫洛里科斯(fmaurolycus,

8、14941575,意大利的数学家、物理学家和工程师)在其1575 年出版的著作算术中描述并使用了数学归纳法.美国数学史家 h伊夫斯的数学史概论（第六版中译本）也认为帕斯卡 1665 年的论文三角阵算术中有数学归纳法的最早的、可被接受的陈述.其实,帕斯卡在给卡卡维(carcavi 卒于 1684年)的一封信中已承认是莫洛里科斯引入了这一方法.近代最新研究表明,不仅帕斯卡0不是数学归纳法的最早发明人,莫洛里科斯也不是最早使用这一方法的数学家,可被晋中学院 xx 学院 20xx 届本科生毕业论文接受的数学归纳法的使用年代比莫洛里科斯更早,十四世纪法国的数学家、天文学家和哲学家莱维本热尔松在其 132

9、1 年出版的代表作计算技术中已经“本质上使用了数学归纳法”,更有资料表明,在中世纪伊斯兰数学中就已经较清楚、广泛(在多种著作中发现)地使用了数学归纳法的归纳推理.中世纪前期的欧洲被称为文化史的“黑暗时代”,文化教育名存实亡,古老学问濒临绝迹,技艺艺术逐渐遗忘,社会秩序严重被毁,暴力宗教肆意顺行.中世纪后期情况有所改观,十字军东征带回了东方文化,并从阿拉伯重新捡回了古希腊文化,此时欧洲数学自身的发展仍然及其缓慢,更多的是传播印度、伊斯兰等东方的数学知识,就连意大利数学家 l斐波那契(lenardo f bonacci,约 11701250,也称比萨的莱昂那多),写于 1202 年的名作算盘书也主

10、要介绍、引证了许多印度、伊斯兰等国的数学知识和数学问题,包括阿拉伯数字的写法、用法,四则运算、方程解法等,这本书作为教材在欧洲各国几乎使用了近 200 年,可见数学知识更新之缓慢.德国数学家和数学史家汉克尔(hhankel,18391873)风趣地形容这一现象,“人们惊奇地发现,莱昂那多给予欧洲的那一磅钱,在 300 年间竟丝毫没有生出什么利息”.jh伊夫斯则称, 十四世纪欧洲相对地是数学上的不毛之地,这不仅因为十四世纪下半叶黑死病扫荡了欧洲三分之一以上的人口,也因为这是一个政治、经济动荡,战争不断的世纪,这种影响一直延续到文艺复兴.如此状况,莱维本热尔松的贡献也算是给中世纪欧洲数学增添了一份

11、光彩.中世纪的伊斯兰则与欧洲大不相同,其商业繁荣,文化活跃,占希腊、印度的数学知识几乎全部传播到那里,被吸收消化并形成自己独特的风格,他们将希腊数学中几何证明的思想,转移到代数学研究中,希望能够证明代数规则的合理性.伊斯兰的代数中充满了证明的思想,很多计算问题都被他们扩展为可以对一般情形也成立的形式, 归纳推理思想(这里的归纳推理指的是数学中的递推,而非普通逻辑中的归纳法的推理)就是在这样一种氛围中被逐步凝炼.2 数学归纳法的原理自然科学中的“经验归纳法”,是从某一现象的一系列特定的观察出发,归纳出支配该现象所有情况的一般规律,而数学归纳法则是迥然不同的另种手段,它用来证实有关无限序列（第一个

12、,第二个,第三个,等等,没有一个情况例外）的数学定理的正确性.16数学归纳法原理:假设我们希望证明一系列无限个数学命题 a1, a2 , a3 ,它们合在一起便构成一般的命题 a .如果a） 通过某种数学论证可以证明,对于任一整数r ,如果命题 ar 已知为真,则命题ar +1 随之亦真;b） 第一个命题 a1 已知为真,那么序列中所有命题必都为真,从而 a 得证.数学归纳法的原理是奠基在下属事实的基础上:在任一整数r 之后接着便有下一个r + 1,从而从整数 1 出发,通过有限多次这种步骤,便能达到任意选定的整数n .推广后的数学归纳法原理:假设给定一系列命题 as , as+1 , as+

13、2 ,其中s 是某正整数,如果a） 对于每个r s , ar+1 的正确性可以从 ar 的正确性导出,b） as 已知为真则所有命题 as , as+1 , as+2 ,均为真;换句话说,对于所有的n s , an 为真.我们再次强调指出,在自然科学中,数学归纳法原理与经验归纳法是完全不同的, 一般的定律如果被证实了任意有限次,那么不论次数多么多,甚至至今尚未发现例外, 都不能说该定律在严格的数学意义下被证明了,这种定律只能算作十分合理的假设, 它容易为未来的经验结果所修正.在数学中,一条定律或一个定理所谓被证明了,指它是从若干作为真理接受的假设出发而得到的逻辑推论.人们考察一个定理,如果它在

14、许多实例中是正确的,那么就可猜想定理在普遍意义下将是真的;然后人们尝试用数学归纳法以证明之.如果尝试成功,定理被证明为真;如果尝试失败,则定理的真伪未定,有待以后用其他方法予以证明或者推翻.因此在应用数学归纳法原理是要牢记 a）和 b）必须真正的满足.3 数学归纳法3.1 数学归纳法的具体表现形式归纳法分为完全归纳法和不完全归纳法,而数学归纳法属于完全归纳法,它又分为有限数学归纳法和超限数学归纳法,前者有两种不同的形式,它们分别叙述为:第一数学归纳法:如果性质 p(n) 在n = 1时成立,而且在假设了n = k 时性质p(k ) 成立后,可以推出在n = k + 1时性质 p(k + 1)

15、也成立,那么我们可以断定性质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(k + 1) 成立”的充分必要条件为“由 p(n) （其中n k ）成

16、立,可以推出 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) 成立的所有自然数0构成一非空子集,记m 为该子集的最小自然数.所以,对任一自然数n ,只要n 1自然数集 n 有最小数1 当1 a , a 有最小数1当1 a 时,假设 a 没有最

17、小数,构造集合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) 成立

18、的所有自然数n 的集合,设t = n - m ,假设t ,根据最小数原理t 有最小数t0 .由条件 p(1) 成立,则1 m . t0 11、2 、t0 - 1 m又由条件 t0 t 矛盾 t m = n p(n) 对任意自然数成立.得证.5 数学归纳法在各门学科中的简单应用5.1 数学归纳法在初等数学中的应用数学归纳法在归纳猜想问题及不等式证明问题中等都有着广泛的应用.例 1 对任意自然数n ,求 1 + 1 +3151 + l +3514n 2 - 1的和.证 明 设的和为 sn ,1 + 1 +3151 + l +3514n 2 - 1则s = 1 + 1 +1 + l +1=1+1+1

19、+l +1.n315354n 2 - 14 12 - 14 22 - 14 32 - 14 n 2 - 1先对n = 1,2,3,4,5 分别进行计算,再寻找其中的规律.显然s =1 , s132= 2 , s53= 3 , s74= 4 , s95= 5 .11s 的下标就是项数,观察s1 s5 ,可以看出他们的分子都与其项数相同.把分母变形,则有或者再写成s =111 + 2, s2=22 + 3, s3=33 + 4, s4=44 + 5, s5=5.5 + 6s =112 1 + 1, s2=22 2 + 1, s3=32 3 + 1, s4=42 4 + 1, s5=5.2 5 +

20、1于是我们就猜想: s= n.再观察 n=6 的情形,有s= 6 =6 ,又符合n2n +16132 6 + 1我们的猜想.再观察一下 n =7,则有s7= 7 =1572 7 + 1.此时我们对于上面的猜想就更有信心了.然而至今采用的还是经验归纳法,要确定 n2n +1是sn的求和公式,还要经过严格的证明.如何证明它呢?这恰好是一个与自然数有关的命题,所以我们不妨试一下数学归纳法.设只要能证得s =nn2n + 1sn+1=n + 1=2 (n + 1) + 1n + 12n + 3即可.事实上sn+1= sn+1=4(n + 1)2 - 1n+2 n + 11=22 (n + 1)2 -

21、1n+2 n + 11(2n + 2 + 1)(2n + 2 - 1)=n(2n + 3)+(2n + 1)(2n + 3)1(2n + 1)(2n + 3)= (2n + 1)(n + 1) =(2n + 1)(2n + 3)n + 12n + 3证毕.5.2 数学归纳法在高等代数中的应用数学归纳法在高等代数中的应用也很突出,这主要是由高等代数内容体系所决定,其中许多证明及行列式的计算等,都要用到数学归纳法.例 2 设是n 阶矩阵,证明行列式2aa 2a = 12a1a 22a1ooa 2a = (n + 1)an .o2a1 a 22a证 明 记2a a 2dn = a =12a1a 22

22、a1ooa 2,o2a1a 22ann下面用数学归纳法证明:当n = 1时, d1 = 2a ,命题 dn = (n + 1)an 正确.当n = 2 时, d2= 2a a 21 = 3a 2a2 ,命题 dn= (n + 1)an 正确.当n k 时,命题 dn = (n + 1)an 正确,对 dk 按第一列展开得2a a 2dk = 2a12a1a 22a1ooa 2o2a1a 22a k -11a 2+ a 2 (-1)2+102a1ooa 2o2a1a 22a k -1= 2adk -1 - a 2 dk -2按归纳假设dk -1 = kak-1 , dk -2 = (k - 1)

23、ak-2 ,从而dk= 2a(kak-1 ) - a 2 (k - 1)ak-2 = (k + 1)ak ,所以n ,命题 a = (n + 1)an 正确.例 3 计算行列式:1cosa11cosa21cosa3ll1cosandn =cos 2a1cos 2a2cos 2a3lcos 2anlllllcos(n - 1)a1 cos(n - 1)a2 cos(n - 1)a3lcos(n - 1)an分析 这个行列式如果直接计算很困难,也很难发现什么规律.但是,如果先从特殊情况入手就容易发现规律.当n = 3 时,d3 =1cosa1 cos 2a11cosa2 cos 2a21cosa3

24、 cos 2a31=cosa1 2cos2 a1 -11cosa2 2cos2 a2 -11cosa32 cos2 a3 -11=cosa1 2cos2 a11cosa2 2cos2 a21cosa3 2cos2 a31= 2 cosa1cos2 a11cosa2 cos2 a21cosa3 cos2 a3= 2 (cosaj - cosai )1i j3这里利用了范德蒙行列式的计算公式. 当n = 4 时,1111cosa1cosa2cosa3cosa4cos 2acos 2acos 2acos 2a4cos 3a1cos 3a2cos 3a3cos 3a4d4 =1231111=cosa1

25、2 cos2 a1 - 14 cos3a - 3cosacosa22 cos2 a2 - 14 cos3a - 3cosacosa32 cos2 a3 - 1 4cos3a - 3cosacosa42 cos2 a4 - 14 cos3a - 3cosa112233441111cosa1cosa2cosa3cosa4= 2 cos2 a2 cos2 a2 cos2 a2 cos2 a12344 cos3a4 cos3a4 cos3a4 cos3a1234ji= 21+2 (cosa - cosa)1i j4由此可以猜想:njid = 21+2+3+l(n-2)(cosa - cosa) = 2

26、1i jn(n-2)(n-1)a -a2(coscos )ji1i jn下面用数学归纳法证明.证明 当n = 3 时,已证,原等式成立.假设3 n k (k 3) 时,原不等式成立,下证n = k + 1时也成立.111l1cosa1cosa2cosa3lcosak +1dn = cos 2a1cos 2a2cos 2a3lcos 2ak +1lllllcos ka1cos ka2cos ka3lcos kak +1将行列式的第k - 1行加到第k + 1行,再将第k 行的- 2 cosa1 加到第k + 1行.然后将第k - 2 行加到第k 行, 将第k - 1行的- 2 cosa1 加到第

27、k 行,依此类推110cosa2 - cosa1dk +1 =02 cosa2 (cosa2 - cosa1 )ll02 cos(k - 1)a2 (cosa2 - cosa1 )l1lcosak +1 - cosa1l2 cosak +1 (cosak +1 - cosa1 )lll2 cos(k - 1)ak +1 (cosak +1 - cosa1 )= (cosa - cosa)(cosa - cosa)l(cosa- cosa)2k-11cosa22131k +111l1cosa2mlcosak +1mcos(k - 1)a2lcos(k - 1)ak +1,由假设得:mcos(k

28、- 1)a211l1cosa2mcosa3mlcosak +1mcos(k - 1)a2cos(k -1)a3lcos(k - 1)ak +1(k -2)(k -1)= 22(cosaj - cosai )2i jk +1从而有:d= (cosa - cosa)(cosa - cosa)l(cosa- cosa)2k -12(k -2)(k -1)a -a2(coscos )k +12131k +11ji2i jk +1k (k -1)= 2 2(cosaj - cosai )1i jk +1所以猜想成立.5.3 数学归纳法在离散数学方面的应用离散数学以离散问题为研究对象其中很多的结论均与自然

29、数有关,并可以运用数学归纳法来证明离散数学中的某些结论,如有关集合中关系及性质、树及其性质等, 这样既降低了证明过程的复杂性,又使推理过程更加严密清晰.n例 4 已知设d1 , d 2 , dn 是n 个正整数, n 2 ,已知di = 2n - 2 ,证明存在结i=1点度数分别为d1 , d 2 , dn 的一棵树.证明 对结点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 ,

30、 dk 的一棵树t1 ,要证n = k + 1时,结论也成立.由d1 , d 2 , dk , dk +1 均为正整数,k +1 di = 2(k + 1) - 2 = 2k 知这k + 1个数中至i=1k +1少有二个为 1,否则 di 2k + 1,与条件矛盾.i=1k不妨设dk +1 = 1 ,于是 di = 2k - 1,这样d1 , d 2 , dk 中至少有一个大于等于 2,i=1k否则di = k 矛盾.i=1k -1k不妨设dk 2 ,于是dk - 1 1 , di + (dk + 1) = di - 1 = 2k - 2 ,i=1i=1考虑d1 , d 2 , dk -1 ,

31、 dk - 1这个正整数,由归纳假设知,存在结点度数分别是d1 ,d 2 , dk -1 , dk - 1的一棵树t1 ,在t 中从度为dk - 1的结点vk 引出一条边,另一端点记为vk +1 ,这样得一棵新树t ,在t 中deg(vk ) = dk , deg(vk +1 ) = dk +1 = 1 .k +1k +1于是deg(vi ) = di = 2(k + 1) - 2 ,因此, t 即为所求的一棵树.ii=15.4 数学归纳法在高等数学中的应用13n12例 5 证明不等式1 + l + 1 2 n (n n ) .证明 (1)当n = 1时,左边= 1,右边= 2 ,左边 右边.

32、不等式成立.(2) 假设当n = k 时,不等式成立,即12kk131 + l + 1 2,当n = k + 1时,则13k1 + kk1 + k121 + l + 1 +1 2+1k + 1k + 1k(现在关键证明2+1 2)kk + 12 k k + 1 + 1k + 1k + 12+1- 2=- 2k + 1k + 1k + 1k + 1k + 1 k + (k + 1) + 1 - 2= 2- 2= 0kk + 1k + 1 2+1 2,即当n = k + 1时,原不等式成立.综合(1)(2)对于任意自然数n 命题成立.例 6 求证cos a cos 2a cos 22 al cos

33、 2n-1 a = sin 2n a (sin a 0)2n sin a证明 (1)当n = 1时,左边sin 2a = 2 sin a cos a = cos a ,2 sin a所以当n = 1时命题成立.2 sin a(2)假设当n = k (k 1) 时命题成立,即:cos a cos 2a cos 22 al cos 2k -1 a = sin 2k a2k sin a将此试的两边同乘以cos 2k a 得:cos a cos 2a cos 22 al cos 2k -1a cos 2k a = sin 2k a cos 2k a2k sin a= 2 sin 2k a cos 2k

34、 a = sin 2k+1a2 2k sin a2k +1sin a所以当n = k + 1时命题成立.综合(1)(2)对于任意自然数n 命题成立.5.5 数学归纳法在图论中的应用例 7大于 7 公斤整公斤的重量都可以仅用一些 3 公斤和 5 公斤两种砝码来称量.证明 只需证明对任意的自然数n 8 ,存在二分图g (n),其 x 顶子集有n 个顶点,每顶皆一次, y 顶子集中的顶是 3 次或 5 次的.下面用数学归纳法证明之.当n = 8 时,结论显然成立,见下图:xx2x6yy1y2x8x7x5x4x3x1假设对于g (k ),结论一成立, k 8 .以下证明对g (k+1),结论仍成立.为

35、此,在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).(ii) 若y 中有 5 次项,设d ( yi ) = 5 ,在 yi 与 xk +1 之间连一边,再把 yi 劈开成两个 3次项,则得满足要求的二分图g (k+1).证毕.5.6 数学归纳法在概率论方面的应用在概率问题中常会遇到一些与实验次数无关的重要结论

36、,这些结论在使用数学归纳法来证明时,常常需要配合使用全概率公式,从而使概率论中的数学归纳法具有自己的特色.例 8 设有n 个罐子,在每一个罐子中各有m 个白球与k 个黑球,从第一个罐子中任取一球放入第二个罐子中,并依此类推,求从最后一个罐子中取出一个白球的概率.解析 先探索规律,设n = 2令 h1 = “从第一个罐子中取出一个球,是白球”h 2 = “从第二个罐子中取出一个球,是白球”显然 p(h1) =m m + k,所求概率p(h 2 ) = p(h1 )p(h 2 | h1 ) + p(h1 )p(h 2 | h1 )=mm + 1+km=m m + k m + k + 1m + k m + k + 1m + k这恰与n = 1时的结论是一样的,于是可以预见,不管n 是什么自然数,所求的概率都应是mm + k ,则当n = t + 1 时,有p(ht +1 ) = p(ht )p(ht +1 | ht ) + p(ht )p(ht +1 | h t )=mm + 1+km=m.m + k m + k + 1m + k m + k + 1m + k于是,结论 p(hn) =m m + k对所有自然数都成立.6 结束语毕业设计,也许是我大学生涯交上的最后一个作业了.想籍次机会感谢四年以来给我帮助的所有老师、同学,你们的友谊是我人生的财富,是我生