数学归纳法原理及其应用举例

《数学归纳法原理及其应用举例》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学校代码：10327本科毕业论文（设计）本科毕业论文（设计）中文题目英文题目数学归纳法原理及其应用举例学院：专业班级：201X年5月18日学号:姓名:指导教师:完成时间:中文摘要英文摘要1弓IW12数学归纳法原理12.1良序原理12.2数学归纳法22.3第二数学归纳法32.4数学归纳法的有效性43数学归纳法应用举例43.1数学归纳法在解题和证明中的一些应用43.2数学归纳法在递归定义上的应用10173.3数学归纳法在递归算法上的应用13参考文献〔学归纳法原理及其应用举例摘要：数学归纳法原理是一种有效的证明方法.木

2、文将介绍数学归纳法及其等价形式,并证明为什么它们是有效的.特别地，我们将用大量各种不同类型的例子来说明其应用这些例子有的来自于集合论，数论，有的来自于计算机科学等.关键词：良序原理，数学归纳法，第二数学归纳法，递归算法.Abstract:Theprinciplesofmathematicalinductionprovideeffectivewaysforvalidargumentsinmathematicalproofs.Thisthesiswillpresenttheseprinciplesandtheirot

3、herequivalentforms，andwillshowwhytheyworkandparticularlywillshowhowtheyworkbyexamplesfromdiversifiedsettingsorareasofmathematics，e.g.settheory,numbertheory，computeralgorithm，andsoon.Keywords:Thewell-orderingprinciple,thefirstprincipleofmathematicalinduction，t

4、hesecondprincipleofmathematicalinduction,recursivealgorithm.1引言首先使用数学归纳法的是意大利数学家和工程师马奥罗修勒斯(FrancescoMaurocyulus,1494-1575),他在1575年的著作《算术》(Arithmetica)中，用数学归纳法证明了前n个正奇数之和是n2.帕斯卡(BlaisePascal,1623-1662)在他关于算术三角形(现在称为帕斯卡三角形)的著作中使用了归纳法.在他1653年的著作《论算术三角形》(Traitedu

5、trianglearithmetique)中，在证明用来定义他的三角形的基木性质时，帕斯卡清晰地解释了归纳法.德摩根在1838年的一篇关于证明方法的论文中，把这个原理命名为“数学归纳法”.前/r个正奇数之和的公式是什么？对72=1，2，3，4，5来说前/r个正奇数之和是1=1,1+3=4，1+3+5=9,1+3+5+7=16,1+3+5+7+9=25根据这些值，有理由猜测前/r个正奇数之和是Y.假如事实上这个猜测是正确的，我们就需要一种方法来证明这个猜测是正确的.数学归纳法是证明这种类型的断言的极为重要的证明技术

6、.2数学归纳法原理2.1良序原理所有数学都始于计数，计数就是把要计数的对象集合与几个起始自然数(或计算值)：1,2,3,4,5...一一对应的过程.我们用7V表示自然数这个无限集合，这里值得注意的是关于2V的定义并未达成共识，有些数学家把0也归入AL但这两种不同定义并不会引起太大的冲突，哪一种使用方便即可选择哪一种.自然数2V的一个基木性质是良序性，下面将对自然数的良序性进行形式化的论述，并且把它作为一个关于2V的公理.对于任何系统，公理是无需证明即为真的命题.为了对一个系统(这里指自然数)进行推理，首先需要对该

7、系统做一些假设.尽管这些基木的假设常常不容易一眼就看出，但它应该是“合理的”和“显而易见为真的”.良序原理：自然数集2V的每个非空子集都有一个最小元素.显而易见，自然数2V的任何子集都可以通过列出实际元素的方式给定，即使对于不易直接定义的集合，该定理依然有效.例如，当x和y可取任意整数时，考虑12x+28y所表示的所有自然数集合.从定义看该集合的范围并不明显，但是根据良序原理，由于该集合非空(注意这很重要)，集合中必有一个通过该方式表示的最小自然数.(当然，求異体的最小自然数的值是另外一回事.注意良序原理保证有一

8、个最小数存在，但绝对没说如何去计算它.)例2.1.1用良序原理证明算法的正确性.整除算法说：若〃是整数而且d是正整数,则存在唯一的整数g和r满足0€r