数学归纳法原理及其应用举例 毕业论文

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

1、目录中文摘要英文摘要1引言……………………………………………………………………12数学归纳法原理………………………………………………………12.1良序原理…………………………………………………………12.2数学归纳法………………………………………………………22.3第二数学归纳法…………………………………………………32.4数学归纳法的有效性……………………………………………43数学归纳法应用举例…………………………………………………43.1数学归纳法在解题和证明中的一些应用………………………43.2数学归纳

2、法在递归定义上的应用………………………………103.3数学归纳法在递归算法上的应用………………………………13参考文献………………………………………………………………17数学归纳法原理及其应用举例摘要：数学归纳法原理是一种有效的证明方法.本文将介绍数学归纳法及其等价形式，并证明为什么它们是有效的.特别地，我们将用大量各种不同类型的例子来说明其应用。这些例子有的来自于集合论，数论，有的来自于计算机科学等.关键词：良序原理，数学归纳法，第二数学归纳法，递归算法.Abstract:Theprinciplesofma

3、thematicalinductionprovideeffectivewaysforvalidargumentsinmathematicalproofs.Thisthesiswillpresenttheseprinciplesandtheirotherequivalentforms,andwillshowwhytheyworkandparticularlywillshowhowtheyworkbyexamplesfromdiversifiedsettingsorareasofmathematics,e.g.s

4、ettheory,numbertheory,computeralgorithm,andsoon.Keywords:Thewell-orderingprinciple,thefirstprincipleofmathematicalinduction,thesecondprincipleofmathematicalinduction,recursivealgorithm.1引言首先使用数学归纳法的是意大利数学家和工程师马奥罗修勒斯（FrancescoMaurocyulus，1494-1575），他在1575年的著

5、作《算术》（Arithmetica）中，用数学归纳法证明了前n个正奇数之和是.帕斯卡（BlaisePascal,1623-1662）在他关于算术三角形（现在称为帕斯卡三角形）的著作中使用了归纳法.在他1653年的著作《论算术三角形》（Traitedutrianglearithmetique）中，在证明用来定义他的三角形的基本性质时，帕斯卡清晰地解释了归纳法.德摩根在1838年的一篇关于证明方法的论文中，把这个原理命名为“数学归纳法”.前个正奇数之和的公式是什么？对，2，3，4，5来说前个正奇数之和是，，，，根

6、据这些值，有理由猜测前个正奇数之和是.假如事实上这个猜测是正确的，我们就需要一种方法来证明这个猜测是正确的.数学归纳法是证明这种类型的断言的极为重要的证明技术.2数学归纳法原理2.1良序原理所有数学都始于计数，计数就是把要计数的对象集合与几个起始自然数（或计算值）：一一对应的过程.我们用表示自然数这个无限集合，这里值得注意的是关于的定义并未达成共识，有些数学家把0也归入.但这两种不同定义并不会引起太大的冲突，哪一种使用方便即可选择哪一种.自然数的一个基本性质是良序性，下面将对自然数的良序性进行形式化的论述，并

7、且把它作为一个关于18的公理.对于任何系统，公理是无需证明即为真的命题.为了对一个系统（这里指自然数）进行推理，首先需要对该系统做一些假设.尽管这些基本的假设常常不容易一眼就看出，但它应该是“合理的”和“显而易见为真的”.良序原理：自然数集的每个非空子集都有一个最小元素.显而易见，自然数的任何子集都可以通过列出实际元素的方式给定，即使对于不易直接定义的集合，该定理依然有效.例如，当和可取任意整数时，考虑所表示的所有自然数集合.从定义看该集合的范围并不明显，但是根据良序原理，由于该集合非空（注意这很重要），集合

8、中必有一个通过该方式表示的最小自然数.（当然，求具体的最小自然数的值是另外一回事.注意良序原理保证有一个最小数存在，但绝对没说如何去计算它.）例2.1.1用良序原理证明算法的正确性.整除算法说：若是整数而且是正整数，则存在唯一的整数和满足和.证明设是形如的非负整数的集合，其中是整数.这个集合非空，因为可以任意大（取是绝对值很大的负整数）.根据良序性，有最小元.整数非负而且.若不是这样，则里存在更小的