浅谈数学归纳法及其应用

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