|
数学归纳法的一点拓广
摘要:本文首先列出了正整数集上的数学归纳法的几种常见形式,写出了数学归纳法的逆否命题,接着将数学归纳法从正整数集逐步推广到复数集及其某些子集,然后指明数学归纳法的实质在于递推,在此基础上又将数学归纳法从等差数集推广到等比数集等良序集,最后又将数学归纳法从普通加法运算推广至一般抽象运算,为数学命题的证明开辟了一条新的道路.文章穿插了一些应用实例.
关键词:数学归纳法;拓广;递推;良序集;抽象运算
中图分类号:O313.1文献标识码:A文章编号:
归纳法是从个别论断归结出一般结论的推理方法,一般性结论的正确性依赖于各个个别论断的正确性,它可以分为完全归纳法和不完全归纳法这两种,完全归纳法只局限于有限的几个元素,而不完全归纳法得出的结论却不一定具有可靠性,因而数学归纳法属于完全归纳法.数学归纳法是一种重要的数学方法,许多专家和学者都对其应用进行了研究.数学归纳法能解决的应用问题有很多,而且它能将复杂问题简单化、非标准型问题标准化,使原来的问题变得容易解决.
数学归纳法是数学中一种重要的解题方法,从普通且不严密的“不完全归纳法”到精确的“数学归纳法”,再到一般的“超穷归纳法”、“连续归纳法”等,数学归纳法至此已经有两千多年的历史了.数学归纳法最早可以在印度和古希腊时代的著作中找到一些痕迹,例如印度婆什迦罗的“循环方法”和欧几里德素数无限的证明中都可以找到这种踪迹.最早的使用数学归纳法的证明出现在意大利数学家莫洛里克斯(1494~1575)的著作《算术》中,它提出了这种方法并证明了.之后数学归纳法便成为数学家们得心应手的数学工具.1889年意大利数学家皮亚诺(C·Peano,1858~1932)发表了《算术原理新方法》,给出了自然数的公里体系,使数学归纳法有了一个准确、合理的理论基础.
李文林翻译的美国数学史教授V·J·Katz在《数学史通论》(第二版)中表明,十四世纪法国数学家、物理学家、工程师莱维·本·热尔森(LevibenGerson,1288-1344)在其1321年出版的代表作《计算技术》中已经“本质上使用了数学归纳法”,更有资料表明的是,在中世纪的伊斯兰数学中就已经较清楚,较广泛地使用了数学归纳法的归纳推理.但真正比较明确的使用数学归纳法的还是意大利物理天文学家、数学家和工程师莫洛里科斯(F.Maurolycus,1494-1575),但他也没有对数学归纳法证明中的奠基和归纳推理这两个步骤进行明确描述.真正的去明确数学归纳法证明两步的应该是17世纪数学家帕斯卡(B.Pascal,1623-1662),他最早的将数学归纳法的证明用形式的两步骤明确下来.“数学归纳法”的名称则是由英国数学家创立的,并由英国教科书作者普遍采用和推广.然而严格意义上的数学归纳法的建立,是在数的理论充分发展及对无穷概念有较深刻的认识后才得以完成的.十七世纪后,在数学归纳法有了明晰的框架后,发展出了最小数原理、第一和第二数学归纳法、反向归纳法、螺旋归纳法、双重甚至多重归纳法等各种形式的数学归纳法.至1889年意大利数学家皮亚诺(C.Peano,1858-1932)发表《算术原理新方法》,给出自然数的公理体系,使数学归纳法有了一个准确、合理的理论基础.
逻辑上的归纳法是指从一系列有限的特殊事例中推出一般性结论的推理方法,从肯定全体对象中一系列有限的个别的事物到肯定全体对象.可是数学归纳法并不具备这些特征.逻辑中的演绎法是由一般性的前提推到个别性结论的推理方法,演绎推进的前提必然蕴涵着结论.无论是从数学归纳法的理论根据上来考察,还是从推理的过程来考察,数学归纳法的本质上都是一种演绎法.现代美国数学家和数学教育家波利亚(G.Polya,1887-1985)曾经这样评论“数学归纳法”这一名称:“归纳法是通过对特例进行观察与综合以发现一般规律的过程.它用于所有科学甚至数学.数学归纳法则仅在数学中用以证明某类定理.从名称上看,二者有联系,但二者在逻辑方面的联系极少.不过两者之间还有某种实际联系;我们常把两种方法一起使用.”虽然说数学归纳法适用于有关整数的问题,但是它在解决很多数学问题中都有重大的作用,在中学数学中,很多不等式问题、几何问题、函数问题、整除性问题用它来解决都能收到很好的效果.时至今日,数学归纳法依然有待补充的问题.前人的研究没有对应用数学归纳法来解题做出具体、详细的分析和评注,对数学归纳法在代数方面的应用的总结和归纳还是有一些欠缺和不足,比较零散,不够深入,很多的文章都只是去片面的书写数学归纳法的应用.本文主要是从数学归纳法应用的范围是从一般的正整数集到良序集.
一、正整数集的数学归纳法的多种形式
数学归纳法是证明正整数集上的有关命题的一种重要论证方法,许多数学命题利用其它数学方法很难证明或者根本无法证明,但是利用数学归纳法很容易得到证明.数学归纳法是一种递归推理,其理论依据就是下列归纳公理:(1)存在一个正整数.(2)每一个正整数
有一个后继元素
,如果
是
的后继元素,则
叫做
的生成元素.(3)正整数1无生成元素.(4)如果
,则
.(5)(归纳公理)自然数
的每个子集
,如果
含有
,并且含有
内每个元素的后继元素,则
.最小数原理:正整数集中的任意一个非空子集必含有一个最小数.也就是说,存在数
,对于
都有
,最小数原理就是数学归纳法的理论依据.
数学归纳法的理论根据式正整数的序数理论,为了证明命题的需要演变成了多种形式,下面列出几种常见形式:
1. 第一数学归纳法原理
定理1:如果关于正整数n的命题p(n)满足:①(奠基)p(n)在n=1时成立;②(归纳)在p(k)成立的假定下,可以推出p(k+1)成立.则p(n)成立对于所有正整数n都成立.
证明:(反证法)假设该命题不是对于一切正整数都成立的.令表示使该命题不成立的正整数作成的集合,那么
.那么由最小数原理,
中有最小数
.因为命题对于
时成立,所以
,
.从而
是个正整数.又由条件(3),当
时命题也成立.因此
,导致矛盾.因此该命题对于一切正整数都成立.定理证明完毕.
例1设有个球分成了许多堆,我们可以任意选甲,乙两堆来按照以下规则挪动:若甲堆的球数
不少于乙堆的球数
,则从甲堆拿
个球放到乙堆去,这样算挪动一次,求证:可以经过有限次挪动把所有的球合并成一堆.
证明:当时,共有2个球,若已成为一堆,则不必挪动;若分成两堆,那么挪动一次便可成功.
假设时命题成立,当
时,对于
个球,若将2个看成1个便退到
个球的情况,这种合并要求每堆球的个数为偶数,讨论如下:若每堆球的个数为偶数,则每挪动一次都是挪动了偶数个球,这样的任意一次挪动与将球两两合并在一起挪动无本质上的区别,从而等价于
个球的挪动,根据归纳假设,这是可以的.若存在球数为奇数的堆,则由总球数为偶数可知,有奇数的堆数为偶数,将它们配对先挪动一次,于是每堆球数都为偶数,问题就可以解决了.
推论1:设p(n)是关于正整数n(n≥n1,n∈N★)的命题,若①(奠基)p(n)在n=n1时成立;②(归纳)在p(k)(k≥n1)成立的假定下,可以推出p(k+1)成立.则p(n)成立对于不小于正整数n1的正整数都成立.
推论2:如果关于正整数n的命题p(n)满足:①(奠基)p(n)在n=1,2,3,……,m时成立;②(归纳)在p(k)(k≥m)成立的假定下,可以推出p(k+1)成立.则p(n)成立对于所有正整数n都成立.
2. 第二数学归纳法原理
如果关于正整数n的命题p(n)满足:①p(n)在n=1时成立;②在p(n)对满足n≤k(k为正整数)都成立的假定下,可以推出p(k+1)成立.则p(n)成立对于所有正整数n都成立.
3. 反向归纳法
设p(n)是关于正整数n的命题,若①p(n)对无穷多个正整数n成立;②在p(k+1)成立的假定下,可以推出p(k)成立.则p(n)对任意正整数n都成立.
设是一个关于正整数
的命题,若
(1)对
、2、3···
成立;
(2)假设成立,可推出
成立;
(3)则对一切正整数
都成立.
例2设和
.
求证:
.
证明:(1)当时,因
,
,所以
,即
,命题显然成立.当
时,由
.可知命题也成立.
(2)假设当时命题是成立的,则当
时,
,即
,可以推出:
=
故当时,命题成立.
(3)于是对于任意的自然数,原不等式成立.
设是一个关于两个独立正整数
有关的命题,若
(1)设成立;
(2)假设成立,可推出
与
成立;
(3)则对一切正整数
成立.
对两个与正整数有关的命题
(1)验证时
成立;
(2)假设成立,能推出
成立,假设
成立,能推出
成立;
(3)综合(1)(2),对一切正整数,
,
都成立.
螺旋式数学归纳法和反向数学归纳法.现在我们把两种数学归纳法结合起来那么就得到了一种新的数学归纳法推广形式.
定理:设和
是与正整数
有关的命题,若
(1)和
都对无穷多个正整数
成立;
(2)存在正整数,对于任意正整数
,假设
成立,则
成立;对于任意正整数
,假设
成立,则
成立.
(4)那么命题和
对于一切正整数
成立.
证明:设使命题不成立的正整数
所成的集合为
.假设
不是空集,根据最小数原理,
中必存在最小数
,于是命题
不成立.因为
对无穷多个正整数
成立,所以总可以找到一个整数
,使得
成立.这样的话,
成立→
成立→
成立→
成立→
成立······经过有限步后,可推得
也成立,这就导致矛盾,故
是空集,所以命题
对所有的正整数
成立.根据(2),对于任意正整数
,当
成立时则
必成立,因此由命题
对所有的正整数
都成立可知命题
也对所有的整数
都成立.综上所述,命题
和
对一切正整数
都成立.证毕.
当然数学归纳法的形式还有很多,有兴趣的读者可参阅其它有关书籍,下面我们思考另一个问题.我们知道,任何一个命题都与它的逆否命题等价,当一个命题很难证明时,我们可以通过证明它的逆否命题成立来证明原命题成立,因此数学归纳法也可以写出其逆否命题,下面以第一数学归纳法为例写出数学归纳法的逆否命题,其它形式的逆否命题从略.
第一数学归纳法的逆否命题:如果关于自然数n的命题p(n)满足:①(奠基)p(n)在n=1时成立;②(归纳)在p(k)(k≥2)不成立的假定下,可以推出p(k-1)不成立.则p(n)成立对于所有正整数n都成立.
二、数学归纳法在整数集上的应用
通过上面分析我们可以清晰地看到:数学归纳法的实质在于递推,数学归纳法之所以能应用于正整数集就在于正整数集是良序集,元素之间具有递推性,因此数学归纳法可以适用于其它良序集.下面举几例数学归纳法的拓广,限于篇幅仅限几种常见形式,而且不再一一写出其逆否命题.
既然数学归纳法应用于正整数集在于正整数集具有初始值1,那么初始值为其他整数也可以.令集合M={n0,n0+1,n0+2,……},n0∈Z,类似于正整数集也可以列出数学归纳法的各种形式及其逆否命题,实际上只要把正整数集中“1”改为n0即可,在此从略.
例3对每个,求证存在
个互不相等的正整数
,使得
,对任意的
成立.
证明:当时,取
,命题显然成立.
假设时命题成立,即存在
满足
,记b为
及它们每两个数之差的最小公倍数,则
个
,
也满足
,
,
,
,
即命题对时成立,由数学归纳法知命题成立.
数学归纳法之所以可以应用于正整数集除了因为正整数集具有初始值,而且由于正整数集成等差数列:公差d=1.既然公差可以为1,自然也可以为-1,因此数学归纳法也可以应用于集合N={n0,n0-1,n0-2,n0-3,……},n0∈Z.
1.第一数学归纳法原理:设有一个关于集合M的命题.如p(n0)成立,而在假定p(k)对于所有x>k的整数n∈M成立的条件下可以推出p(k).那么对于任意整数n∈M,p(n)都成立.
推论1:设p(n)是关于数集M的命题,若①(奠基)p(n)在n=n0时成立;②(归纳)在p(k)(k≤n0)成立的假定下,可以推出p(k-1)成立.则p(n)在数集M上成立.
推论2:设p(n)是关于数集M的命题,若①(奠基)p(n)在n=n0,n0-1,n0-2,n0-3,…,n0-l+1时成立;②(归纳)在p(k)(k∈M)成立的假定下,可以推出p(k-1)成立.则p(n)对于数集M都成立.
2.第二数学归纳法原理:设有一个关于数集M的命题.如p(n0)成立,而在假定p(k)对于所有x>k的整数n∈M成立的条件下可以推出p(k)成立.那么对于任意整数n∈M,p(n)都成立.
3.反向归纳法原理:设p(n)是关于数集M的命题,若①p(n)对于集合M中无穷多个整数均成立;②在p(k-1)成立的假定下,可以推出p(k)成立.则对于任意整数n∈M,p(n)都成立.
4.第一数学归纳法原理的逆否命题:设有一个关于数集M的命题,若①(奠基)p(n)在n=n0时成立;②(归纳)在p(k)(k≤n0)不成立的假定下,可以推出p(k-1)不成立.则p(n)在数集M上成立.
为了证明这些原理,先定义数集M的序数理论.
定义:集合M里的某些元素之间有一基本关系“前继”(`a=a-1)满足下面的公理:①存在着数n0,它不前继于任何数(即n0∈M,对于任何数a∈M,`a≠n0);②除n0以外,对任何一个数a∈M,存在着一个且仅存在一个前继数`a(即a∈M,则有一个且仅有一个`a存在,且`a∈M);③除n0以外,任何数只能是一个数的前继数(即`a=`b,应有a=b);④(归纳公理)设M有一个子集N,满足条件:n0∈N;若a∈N,有`a∈N,则N=M.
证明:1.第一数学归纳法原理
设N是所有命题p(n)成立的整数n∈M的集合,于是①因为p(n0)成立,故得n0∈N;②因为假定p(k)成立的条件下,能推出p(k-1)成立(即p(`k成立).这就是说,如果k∈N,能推得`k∈N,即集合N具有定义中的归纳公理的两个条件①和②,由归纳公理得N=M,这就是说命题p(n)对于任意整数n∈M成立.
2.推论的证明:推论1的证明类似于上面证明不大于n1的元素都成立,将剩余元素列举证明即可.
推论2的证明:①由10知在n=n0时命题成立;②由20知假定p(k)成立时,可以推出p(k-1)成立,所以令k=n0,n0-1,n0-2,n0-3,、、、,n0-l+1,得p(n0-l),p(n0-l-1),p(n0-l-2),p(n0-l-3),、、、,p(n0-2l+1),这样依次地推下去,每隔l个数为一周期下去,可知p(n)对于任意整数n∈M成立.
3.第二数学归纳法原理
假设p(n)不是对于任意整数n∈M成立,由定义可知,在那些使p(n)不成立的所有整数n∈M的集合中必存在最大数,设为n1(n1<n0),这样对n1<x<n0来说,一定会使p(n)成立.在此结论下,由第二数学归纳法原理中的假设可知p(n)对n1来说一定成立,这与前面假设n1是使p(n)不成立的所有整数n∈M的集合中的最大数矛盾.这个矛盾说明了p(n)对所有整数n∈M都成立.
4.反向归纳法
设m为集合M中的任一整数,已知由无穷多个数集M中的整数使p(n)成立,故其中必能找到一个整数l∈M,使l≤m-1.设Q(n)=p(l+n-n0),则Q(n0)=p(l+n0-n0)=p(l)成立,即Q(n)当n=n0时成立.又据20,由p(k-1)成立可以推出p(k)成立,所以由p(l+k-n0)成立可以推出p(l+k-n0+1)成立,注意到p(l+k-n0)=Q(k),p(l+k-n0+1)=Q(k+1).因此根据第一数学归纳法,Q(n)对一切整数n∈M都成立.特别地,取n=l+m-n0,有Q(l+m-n0)=p(m)成立.因为m为集合M的任意整数,所以p(n)对所有整数m∈M都成立.
数学归纳法既然可以应用于M={n0,n0+1,n0+2,……}和N={n0,n0-1,n0-2,n0-3,……},n0∈Z.取两个集合的并集便得到整数集.因此若先分别归纳,便可以对整数集做出了归纳,不过此时一定应先取一个整数n0验证原命题成立,证明过程类似于上面,在此从略.
数学归纳法应用于整数集不但可以分两步进行归纳,而且可以将其合并为一步,为此先定义整数集的序数理论.
定义:任何一个非空集合Z的元素叫做整数,如果在这个集合里的所有元素之间有两种基本关系——“前继”与“后继”,满足下面的公理:①对任何一个数a,存在着且仅存在着后继数a`与前继数`a;②任何一个数只能是一个数的后继数与另一个数的前继数;③存在a∈N,且a∈Z;④(归纳推理)设Z有一个子集M,满足条件:Z0∈Z,且Z0∈M;若a∈M,有后继数a`∈M与前继数`a∈M.则M=N
1. 第一数学归纳法原理:设有一个关于整数Z的命题p(Z),①存在Z0∈Z,使p(Z0)成立;②在假定p(k)成立的条件下,能推出p(k-1)与p(k+1)均成立.那么对于任意整数Z,p(Z)都成立.
证明:设M是所有命题p(Z)成立的整数集合,于是:①存在Z0∈Z,使p(Z0)成立,故得Z0∈M;②因为假定p(k)成立的条件下,能推出p(k-1)与p(k+1)均成立(即p(`k)和p(k`)成立.这就是说k∈M能推得`k∈M和k`∈M,因此集合M具有整数定义中的归纳公理的条件①、②,由归纳公理得M=Z,这就是说对于任意整数Z,p(Z)都成立.
第一数学归纳法原理的逆否命题:设有一个关于整数Z的命题p(Z),①存在Z0∈Z,使p(Z0)成立;②在假定p(k)不成立的条件下,能推出p(k-1)与p(k+1)不成立.那么对于任意整数Z,p(Z)都成立.
2.推论:设有一个关于整数Z的命题p(Z),存在Z0∈Z,如p(Z0)、p(Z0±1)、p(Z0±2)、、、、、、p(Z0±L±1)成立,而在假定p(k)成立的条件下,可以推出p(k±1)均成立.那么对于任意整数Z,p(Z)都成立.
证明:设M是所有命题成立的整数集合,于是:①因为存在Z0∈Z,p(Z0)、p(Z0+1)、p(Z0+2)、、、、、、p(Z0+L-1)成立;而由p(k)成立可以推出p(k+1)成立,所以对于任意整数m∈{n0,n0+1,n0+2,、、、、、、},p(Z)均成立.②因为存在Z0∈Z,p(Z0),p(Z0-1),p(Z0-2),、、、、、、,p(Z0-L+1)成立;而由p(k)成立可以推出p(k+1)和p(k-1)成立.所以对于任意整数m∈{n0,n0-1,n0-2,、、、、、、},p(Z)均成立.由①、②可知对于任意整数Z,p(Z)都成立.
3.第二数学归纳法原理:设有一个关于整数Z的命题p(z).若①存在Z0∈Z,使p(Z0)成立;②设x∈{x|k1〈x〈k2,k1和k2为整数},而在假定p(x)[x∈{x|k1〈x〈k2,k1和k2为整数}]成立的条件下,可以推出p(k1)和p(k2)成立.那么对于任意整数Z,p(z)都成立.
证明:假设p(z)不是对于所有整数均成立,根据整数集的序数理论,可以找到一个整数Z1(不妨设Z1≥k2,当Z1≤k1时证明类似),使p(Z1)不成立,而p(Z1-1)成立.根据归纳假设得由p(x)[x∈{x|k2〈x〈Z1-1,k1和k2为整数}(k2,Z1-1)]成立,得p(Z1)成立,这与前面的假设p(Z1)不成立相矛盾.故对于任意整数Z,p(Z)都成立.
既然数学归纳法可以应用于整数集实质在于整数集中相邻两数的公差为定值1,那么当然它也可以应用于其他公差为定值或公差为统一公式的某些数集,如奇数集或偶数集,也可以建立其序数理论,方法及证明类似于整数集,只不过将k±1变成k±2即可.
综上所述,数学归纳法可以应用于整数集及其某些子集,而数论主要是研究整数性质的,所以数学归纳法对于数论的发展可能会起到一定作用,同时也可以将某些关于自然数集的命题推广至整数集或其某个子集,而且有的命题运用其他方法可以证明,但是不如数学归纳法来得清晰、思路简单.
我国著名的科学家钱学森说过:“世界上任何发明创造都是可及的,不是不可及的.现在中国没有完全发展起来,一个重要原因是没有一所大学能够按照培养科学技术发明创造人才的模式去办学,没有自己独特的创新的东西,老是‘冒’不出杰出人才.这是很大的问题.中国还没有大学能够按照科学技术发明创造人才的模式去办学,都是人云亦云,一般化的,没有自己独特创新的东西,受封建思想影响,一直是这个样子.别人说过的才说,没说过的就不敢说.你是不是真正的创新,或者敢不敢研究别人没有研究过的科学前沿问题,而不是别人说过的我们知道,没有说过的东西我们就不知道.所谓优秀的学生就是要创新,没有创新,死记硬背,考试成绩再好,也不是优秀学生.”
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-8-1 13:16
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社