LUOYANG NORMAL UNIVERSITY 2013届本科毕业论文数学归纳法及其在初等数论中的应用院（系）名称数学科学学院专业名称数学与应用数学学生姓名孙xx学号110412016指导教师xx 讲师完成时间2013.5数学归纳法及其在初等数论的应用孙xx数学科学学院数学与应用数学学号：110412016指导教师：xx摘要：数学归纳法是一种非常重要的数学证明方法,典型的用于确定一个表达式在所有自然数范围内是成立的或者用于确定一个其他形式在一个无穷数列是成立的.本文通过直接证法引入数学归纳法,并介绍了数学归纳法的两个基本步骤及原理.初等数论研究的是关于整数的问题,故应用数学归纳法证明初等数论中的有关的命题是重要的途径.关键词：数学归纳法;初等数论;不定方程;整除;同余1 引论1.1 直接证法众所周知,数学上的许多命题都与自然数有关.这里所指的n,往往是指任意的一个自然数.因此,这样的一个命题实际上也就是一个整列命题.要证明这样一整列命题成立,当然可以有多种不同的方法.其中常用的方法是置n的任何具体值而不顾,而把它看成是一个任意的自然数,也就是说,假定它只是任何自然数都具备的共同性质,并且在这样的基础上进行推导、运算.如果我们在推导运算中没有遇到什么难以克服的困难,那么我们就有可能用这种方法来完成命题的证明了.这种方法就是习惯上所说的直接证法.如下例：例1 已知）（2;,,2,1≥⋅⋅⋅=∈n n i R x i ,满足121=+++n x x x ,021=+++n x x x .证明nn x x x n 2121221-≤+++ . 证 由条件121=+++n x x x 知1x ,2x , ,n x 不全为零;由条件021=+++n x x x 知这n 个实数中既有正数也有负数.记{}0:1≥=i x i A ,{}0:2<=i x i A .则1A 和2A 都不是空集,它们互不相交,且1A ⋃2A ={1,2,3, ,n }.若再记1S =∑∈1A i i x ,2S =∑∈2A i i x , 就有1S +2S =0,1S -2S =1.因此知1S =-2S =21.采用所引入的符号,就有 ∑∑∈∈+=+++21221A i i A i i n i x i x n x x x .由1A 和2A 的定义和性质知∑∈1A i i i x 是若干非负数之和,∑∈2A i i i x 是若干负数之和,因此就有 ∑∑∑∑∑∈∈∈∈=+≤+=222111A i i A i i A i i A i i n i i x n x i x i x i x =nS S 21+=n 2121-=n 2121-. 可见命题的结论是成立的. 在这个证明中,我们没有考虑n 究竟是几的问题,只是把精力花费在对命题条件的推敲和剖析上.这种证法就是直接证法．1.2 数学归纳法有时,我们也会碰到一些与n 有关的命题,对于它们很难从任意的n 入手,那么我们就只能另辟蹊径,也就是所谓的数学归纳法.如下例：例2 证明对于每个不小于3的自然数n ,都可以找到一个正整数n a ,使它可以表示为自身的n 个互不相同的正约数之和．分析 显然,我们很难对任意一个不小于3的自然数n ,直接去找到出相应的n a 来.面对这样的情形,较为稳妥的做法只能是先从3a ,4a , 找起.经过不多的几步探索,就可以发现,有3216++=.而且1,2,3恰好是6的3个互不相同的正约数,因此可将3a 取作6.在此基础上,又可发现有632112+++=.而且1,2,3,6恰好又是12的4个互不相同的正约数,因此又可取124=a ．循环下去,便知可依次取24,48, ．这也就告诉我们：如果取定了k a ,那么接下去就只要再取k k a a 21=+就行了.证 当3=n 时, 3216++=.假设当k n =时成立,即k a 可以表示成自身的k 个互不相同的正约数k b b b <<< 21之和,即k k b b b a +++= 21.取定k k a a 21=+,则：k k k a b b b a ++++=+ 211.若记k k a b =+1,则显然有121+<<<<k k b b b b ,即互不相同且是1+k b 的正约数. 故由第一类数学归纳法得此命题正确.由上所述,数学归纳法可以处理像例2那样不宜于采用直接证法的问题,也可以处理一些可以通过直接证法来解决的问题.如下例:例3 证明:对任何自然数n ,数15231n n -+⋅+能被8整除.若用直接证法,则如下：证 按照n 的奇偶性,可以将上式表示两种不同的形式.当n 为奇数时,有()()15331n n n -+--.当n 为偶数时,有()()1155331n n n --+--.于是上述两式中,第一个括号内的指数都是奇数,第二个括号内的指数都是偶数. 而当k 为奇数,则有))((121---++-+=+k k k k k b b a a b a b a .当k 为偶数,则12-c 可整除1-k c .当5=a ,3=b ,3=c ,可根据上式得出两式是8的倍数.从而命题得证.若用数学归纳法,则如下：证 当1n =时,152318n n -+⋅+=能被8整除.假设k n =时,k A 能被8整除.则当1+=k n 时,我们有=+1k A 15231k k ++⋅+=-155631k k ⋅+⋅+.所以就有)35(411-++=-k k k k A A .由于对任何自然数k ,数k 5和13-k 都是奇数,所以其和135-+k k 恒为偶数. 从而)35(41-+k k 一定是8的整数.即)35(411-+++=k k k k A A 可被8整除.由第一类数学归纳法,对任何自然数n ,数n A 都可被8整除.1.3 初等数论初等数论是数的规律,特别是整数性质的数学分支,它是数论中的最古老的分支.其它的组合数论、解析数论、代数数论、几何数论、超越数论都是在初等数论的基础发展起来的.初等数论是一门十分重要的数学基础课,小学阶段就有初等数论的影子.初等数论不仅是师范院校数学专业,大学数学各专业的必修课,也是计算科学,密码学等许多相关专业所需的课程.2 数学归纳法的原理2.1 第一类数学归纳法定理1 设)(n p 是关于自然数n 的命题,如果)(n p 满足:(1))(0n p 成立;(2)假设当k n =时,命题)(k p 成立,可以推出)1(+k p 成立,则命题)(n p 对一切自然数n 都成立.证 假设命题)(n p 仍不能对一切自然数n ≥0n 成立,那么如果记{}不成立，)(:01n p n n n A ≥=.{}成立，)(:02n p n n n A ≥=.则有Φ≠1A .但因已证)(0n p 成立,知0n ∉1A ,即有20A n ∈. 由于1A 是非空的自然数集合,所以由自然数的最小数原理,1A 有最小数1n . 由于10A n ∉,所以01n n >,即有011n n ≥-.由于1n 是1A 中最小的数,所以111A n ∉-,从而211A n ∈-. 故当11-=n n 时)(n p 成立.记11-=n k ,则由条件(2)知11n k =+时)(1n p 成立,则与11A n ∈矛盾. 故1A 为空集.也就是说,有)(n p 对一切自然数n 都成立.例4 设()nk n n k S 12531-++++= ,2mod 0≡n ,*∈N k ,试证： 1>k 时,k k S 12-.证 当1=k 时,结论显然成立.假设1-=k n 时结论成立,即当()nk n n k S 1253111-++++=-- ,2mod 0≡n ,1>k 时, 122--k k S .现证等于k 时结论成立.由于()()()n k n k nk k k S S 123212111-+++++=---- ()[]()[]()nk n k k n k k 1232212211-++--+--=-- ()[]1)32()12(111++-+--≡-- n k n k n 又因2mod 0≡n ，故上式：k k S 2mod 1-≡.即k k k S S 2mod 21-≡,但122--k k S ,故推得k k S 12-.由第一数学归纳法知,命题对一切正整数k 都成立.2.2 第二类数学归纳法定理2 设)(n p 是关于自然n 的命题,如果)(n p 满足:(1))1(p 成立;(2)假设)(n p 对于所有满足k a <的自然数a 成立时,则)(k p 也成立,那么,命题)(n p 对一切自然数n 都成立.证 设(){}N n n p n M ∈=成立，|,又设M N A -=,假设A 不空, 由自然数的最小数原理,A 有最小数0a ,又由条件(1)M ∈1,故10≠a ,因此1,2,M a ∈-1,0 .又由条件(2)知M a ∈0,这与A a ∈0矛盾,故A 为空集,从而N M =,则命题)(n p 对一切自然数n 都成立.例5 设数列1p ,2p , ,n p , 是由小到大的顺序排列的素数序列.试证n n p 22<. 证 当1=n 时,第一个素数是2,有12122<=p ,命题成立.假设当k n ≤≤１时,命题成立.即1212<p ,2222<p ,…, k k p 22<. 则有kk p p p 2222122221 <,所以 1121222222212221++<=≤+-+++k k k k p p p .上式左边1p 2p …k p +1本身即小于122+k ,其素因数当然更小于122+k ,但它的素因数不可能为1p ,2p ,…,k p ,所以它的素因数必大于或等于1+k p ,因此有1212+<+k k p .所以,由第二数学归纳法知,对一切正整数n p 命题都成立.2.3 跳跃数学归纳法定理3 设)(n p 是一个表示与正整数n 有关的命题,如果)(n p 满足(1)当2,1=n 时,)1(p 和)2(p 都成立;(2)假设当k n =时,命题)(k p 成立,则当2+=k n 时,命题)2(+k p 也成立,那么)(n p 对于一切自然数n 都成立. 证 (用反证法)设)(n p 不是对所有自然数都成立,那么使)(n p 不成立的自然数集为(){}N n n p n M ∈=不成立，|,根据最小数原理,M 中一定存在一个最小的自然数k . 由条件(1)可知1≠k 和2≠k 于是2>k ,令21+=k k ,则1k 满足)(1k p 成立.由条件(2)可知)(1k p 成立,则)2(1+k p 也成立,即)(k p 成立.此与假设)(k p 不成立相矛盾. 故)(n p 必对一切自然数n 都成立.上述结论可以推广到一般情形,即:设)(n p 是一个表示与正整数n 有关的命题,t 为某一自然数()2≥t .如果(1)当t n ,,2,1 =时,命题)1(p ,)2(p , ,)(t p 都成立;(2)假设当k n =时,命题)(t p 成立，则当时t k n +=命题)(t k p +也成立,那么命题)(n p 对一切的自然数n 都成立.例6 证明对一切自然数n ,都存在自然数n x 和n y 使得n n n y x 199322=+. 证 当1=n 时,取431=x ,121=y 即可,因此19931441849124322=+=+. 当2=n 时,注意到1993124322=+,因此只要令17051243222=-=x ,1032124322=⋅⋅=y ,那么就有22222210321705+=+y x =21993.故当1=n ,2=n 也成立.假设当k n =时存在自然数k x 和k y ,使得k k k y x 199322=+, 那么显然就有2221993)1993()1993(+=+k k k y x , 可取k k x x 19932=+,k k y y 19932=+.即只要k n =时断言成立,即可推得2+=k n 断言也成立． 综上所述,知对一切自然数n 断言都成立.2.4 反向数学归纳法定理4 设)(n p 表示一个与自然数有关n 的命题,若(1))(n p 对无数多个自然数n 都成立;(2)假设)(k p 成立,可推出)1(-k p 也成立;那么)(n p 对一切自然数n 都成立.证 (用反证法)设所有使命题)(n p 成立的自然数集合为A ，所有使命题)(n p 不成立的自然数集合为B .如果B 不是空集,可在B 中任取一个数0b ,因A 时无穷集，所以在A 中总能可以找到一个数00b a >.所以由条件(2),)(0a p 为真可得)1(0-a p 为真又得)11(0--a p 为真等等,经过有限步之后,总可使)(0b p 也为真,这与假设矛盾，即B 是空集，故命题)(n p 对所有的自然数n 都成立.例7 设p 是素数,而正整数m 与p 互素,试证:p m p mod 11≡-. 证 问题等价与要证:如果p 是素数,那么对任意正整数m ,有p m m p mod ≡. 令()*N L Lp m ∈=,则()p Lp Lp pmod ≡,即有无穷多个正整数()*N L Lp ∈使得 p m m p mod ≡,假设1+=k m 时, ()()p k k pmod 11+≡+.则由 ()1112-2++++=+-k C k C k k p p p p p p ,()())11(mod 0!11-≤≤≡+--p i p i i p p p , 知()p k k k p pmod 111+≡+≡+. 故p k k p mod ≡.从而根据反向归纳法,对任意正整数m ,有p m m p mod ≡.2.5 二重数学归纳法定理5 设),(j i p 为与自然数i 和j 相关联的命题函数.如果(1)当0i i =,0j j =时,命题),(00j i p 成立.(2)对任一0i k ≥,任一0j l ≥,假定),(l k p 成立,则),1(l k p +和)1,(+l k p 都成立,那么),(j i p 对一切的0i i ≥和0j j ≥都成立.证 i ,j 两次运用第二数学归纳法.当0i i =时,命题()j i p ,0对0j j ≥都成立.事实上,由条件(1),有0j j =时),(00j i p 成立.由条件(2),假设对任意0j l ≥,()j i p ,0成立,则()1,0+j i p 也成立. 由第二数学归纳法,命题()j i p ,0对任意0j j ≥都成立.假设对任一0i k ≥,命题()j k p ,对0j j ≥时成立,),1(j k p +对0j j ≥也成立. 事实上,由条件(2),对任意的0i k ≥,0j j ≥,假定()j k p ,成立则),1(j k p +也成立. 根据第二数学归纳法，命题),1(j k p +对一切0i i ≥和0j j ≥都成立.证毕.例8 试证),(2为自然数n m m n mn >.证 设),(n m p 是与自然数n m ,相关的命题函数. 当1==n m ,有1112>,显然)1,1(p .假设对任一1≥k ,1≥l ,),(l k p 为真,即l kl k >2成立. 下面证明),1(l k p +和)1,(+l k p 都成立.()()()ll l l kl l kl l k k k k 12222221+≥≥⋅>⋅==++. 即有),1(l k p +成立.()1122222+++≥⋅>⋅>⋅==l l k l k kl k kl l k k k k k .即有)1,(+l k p 成立.由二重归纳法可知,对任意的1,1≥≥n m ,),(2为自然数n m m n mn >.2.6 第一类数学归纳法和第二类数学归纳法之间的关系 定理6 第一类数学归纳法和第二类数学归纳法等价.证 假设性质)(n p 在1=n 时成立.则可以转化为：“由数学归纳法及其应用,假设当k n =时,命题)(k p 成立,则可以推出)1(+k p 成立”的充分必要条件为“由)(n p （其中k n ≤）成立,可以推出)1(+k p 成立”.[必要性] 由已知“由)(k p 成立,则可以推出)1(+k p 成立”. 假设k n ≤时)(n p 成立,特别)(k p 成立,所以)1(+k p 成立.得证.[充分性] 由已知k n ≤时)(n p 成立,可以推出)1(+k p 成立. 于是,由)(0k p 成立推不出)1(0+k p 成立的所有自然数0k 构成一非空子集,记m 为该子集的最小自然数.所以,对任一自然数n ,只要m n <,那么由)(n p 成立可以推出)1(+n p 成立. 特别,由)1(p 成立可知)2(p 成立,…,由)1(-m p 成立可知)(m p . 已知)1(p 成立,因此)1(p 、)2(p 、…、)(m p 都成立,然而由此可知)1(+m p 成立,所以从)(m p 成立推出了)1(+m p 成立；另一方面,由m 的选取可知,由)(m p 成立推不出)1(+m p 成立,这就导出矛盾,得证.3 数学归纳法原理在初等数论中的应用初等数论是研究整数性质的一门理论,大致分为整数理论、整除理论、同余理论、不定方程,而数学归纳法就是关于解决自然数的数学方法,故初等数论的多数定理,习题都是通过数学归纳法证明,例如最基本的算术基本定理就是用第二数学归纳法证明.3.1 整除性整除性理论是初等数论的基础.利用数学归纳法解决初等数论中有关整除问题,可以解决众多问题.例9 设集合()n a a a ,,,21 为n 元正整数集N n ∈,2=n .证明()∏≤<≤-n k l l k a a 1能被()∏≤<≤-n k l l k 1整除.证 当2=n 时, 1=l ,2=k .易证结论成立.假设命题对于)3(1≥-n n 的情形成立.即对任意1-n 元整数集合()121,,,-k a a a ,满足 ()∏-≤<≤-11n k l l k a a 被()∏-≤<≤-11n k l l k 整除.下面证命题关于n 的情形也成立. 令()()N p p p p l k i i l n k l l ∈=-∏-≤<≤αααα为质数， 212111,若设()ii r n p =-)!1(,则n 元正整数集()n a a a ,,,21 中存在一个整数(不妨记为n a )使得)())((121----n n n n ri a a a a a a p i .若()'=⎪⎪⎭⎫ ⎝⎛-∏-≤<≤i n k l i r l k p 11,则由归纳假设,得 ()⎪⎪⎭⎫ ⎝⎛-∏-≤<≤'11n k l l k r i a a p i . 即可得：∏≤<≤'+-n k l l k r r i a a p i i 1)(.因为()⎪⎪⎭⎫ ⎝⎛-=∏≤<≤n k l l k i i a a p 1α ()()⎪⎪⎭⎫ ⎝⎛--=∏≤<≤n k l l k i a a n p 1!1()()().!11'+=⎪⎪⎭⎫ ⎝⎛--=∏≤<≤i i n k l l k i i r r a a p n p所以()() ,3,2,11'=-∏≤<≤+i a a p n k l l k r r i i .又因11αp ,22αp , ,l l p α两两互质,所以()∏≤<≤-n k l l k l a a p p p l12121ααα .又()l l n k l p p p l k ααα 212111=-∏-≤<≤.故 ()()∏∏≤<≤≤<≤--n k l l k n k l a a l k 11.由第一类数学归纳法结论成立.例10 证明存在正整数m ,使得()()9372+⋅+=n n n f 对任意自然数n 都能被m 整除?若存在,求出最大的m 值,并证明你的结论.证 当1=n 时有()()3693721=+⋅+=f ,当2=n 时有()()363108937422⨯==+⋅+=f ,当3=n 时有()()3610360937633⨯==+⋅+=f ,由此推想存在正整数m ,且m 的最大值为36,即对任意的自然数n ，)(n f 都能被36整除.当1=n 时明显有命题成立；假设当k n =时有命题成立,即()()9372+⋅+=k k k f 能被36整除.那么当1+=k n 时有()()[]9371211+⋅++=++k k k f()183********-⋅⋅+⋅+⋅+=k k k()()131********-+⋅+⋅+=-k k k .由于131--k ()2≥k 是2的倍数,故有()13181--k 是36的倍数.即()13181--k 能被36整除,由假设得()1+k f 能被36整除.即命题成立,故存在最大的正整数m ,且m 的值为36.3.2 不定方程不定方程是指未知数的个数多于方程的个数的式子,是数论的一个分支,它有着悠久的历史与丰富的内容.早在公元3世纪古希腊的丢番图就开始研究不定方程.著名费马大定理,就是关于不定方程的问题.他在阅读丢番图《算术》时写到:将一个立方数分成两个立方数之和,或一个四次幂分成两个四次幂之和,或者一般地将一个高于二次的幂分成两个同次幂之和,这是不可能的.关于此,我确信已发现了一种美妙的证法 ,可惜这里空白的地方太小,写不下.也就是:当3≥n 时,不定方程n n n z y x =+ 没有正整数解.这个问题困扰了数学家几百年,至到英国数学家安德鲁⋅怀尔斯的出现.可见,不定方程是数论的重要一部分.不定方程一般要解决三个问题:一是判断何时有解,二是决定解的个数,三是求出所有的解.我们就可以利用数学归纳法解决问题.如下例:例11 证明对一切自然数n ,不定方程n z y x =+22都有正整数解.证 当1n =时,取1==y x ,2=z .当2=n ,取3=x ,4=y ,5=z .即满足方程,故知命题1=n 和2时成立.假定当k n =时,0x x =,0y y =,0z z =是方程的一组正数解;那么当2+=k n ,只要取00z x x =,00z y y =,0z z =,则有()()()20202020200200+=+=+k z z x z z y z x .知它们恰为方程的一组正整数解,所以当2+=k n 时,命题成立.由于采用了两个起点,所以可以用两个跳跃,这表明对一切自然数n ,不定方程都有正整数解,证毕.3.3同余在日常生活中,我们所要注意的常常不是某些整数,而是这些数用某一固定的数去除所得的余数.例如问现在是星期几,就是问用7去除某一个总的天数所得的余数.这样,就在数学中产生了同余概念.同余理论是初等数论的重要组成部分,是研究整数问题的重要工具之一,利用同余来论证某些整除性的问题是很简便的.同样,我们可以数学归纳法来研究同余问题.如下所示:例12 已知11=a ,22=a ,而当3≥n 时有⎩⎨⎧⋅-⋅-=--------为奇数若为偶数若21212121,,,35n n n n n n n n n a a a a a a a a a 证明对一切自然数n ,都有0≠n a .分析 在这里显然有01≠a ,02≠a .但若假设01≠-k a ,0≠k a ,却很难有所给的递推关系式断言01≠+k a .可见就原命题证明原命题也很难奏效.我们可以多演算几项,最初的一些项依次是：1,2,7,29,22,23,49,26, .它们显然都是不为零,不过其中既有奇数,也有偶数.但是,我们求同余,可以得出依次是被4除的余数是1,2,3,1,2,3, ,有着非常明显的规律.这就启发我们猜测,可能对一切n ,都会有4mod 123≡-n a ,4mod 213≡-n a ,4mod 33≡n a .如果这一猜测真能成立,那么数列中的一切项当然也就不可能成为零了.证 显然4m od 11≡a ,4m od 22≡a ,4mod 33≡a ,故在1=n 时成立.假设当k n =时,我们的猜测也成立,即有：4mod 123≡-k a ,4mod 213≡-k a ,4mod 33≡k a .那么当1+=k n 时,由递推公式可知4m od 196153513313≡≡-≡-≡-+k k k a a a ；4m od 223131323≡-≡-≡-≡++k k k a a a ；4m od 3731035132333≡≡-≡-≡+++k k k a a a .这就表明,当1+=k n 时,我们的猜测也正确.故知对一切n ,0≠n a .3.4 初等数论中的不等式例13 若x 是一个正实数,n 是一个正整数,证明：[][][][][]nnx x x x nx ++++≥ 33221. 证 设[][][][]k kx x x x x k ++++= 33221,则[]kkx x x k k +=-1.当1=n 时,显然有[][]11x x x =≥.假设不等式1-≤k n 时都成立,即[]()1,,2,1-=≤k i ix x i .考虑k n =时的情形.由于()[]kx x x k kx k k k ++-=--111,()()()[]x k x x k x k k k k 121221-++-=----,[]x x x x 323223++=,[]x x x x 22112++=,将以上各式两边分别相加,得[][][]x x kx x x x x x kx k k k 2311221+++++++++=-- ,由归纳假设,[]()1,,2,1-=≤k i ix x i ,则()[]()[][][][][][][]x x kx x x x x k x k kx k 23221++++++++-+-≤()[][]()()[][]()[]()[]()[]kx x k x x x k x x k +-++++-++-=1221 .由[][][]b a b a +≤+,则[][][][]kx k kx kx kx kx k =+++≤ .故[]kx x k ≤.即k n =时不等式成立,从而对任意的自然数n ,都有[][][][][]nnx x x x nx ++++≥ 33221. 4 数学归纳法在初等数论中注意的问题数学归纳法的两个步骤中,我们通常将验证)(0n p 成立称作起步;将假设条件成为归纳假设,而将由归纳假设推出)1(+k p 也成立的过程叫做归纳过渡.这几步缺一不可.如果使用不当就可能导致错误.4.1 起步错误在数学归纳法的基本形式之下,第一步通常总是由验证)(0n p 成立开始,但是往往容易忽略,觉得无关紧要,可有可无,不去认真的验证这一步,或者根本没有这一步,都可能陷入错误之中,推出看似正确的答案.如下例：例14 试讨论n 2与2n 的大小.错解 由1=n 时,2112>;2=n 时,2222=.假设当k n =时,22k k >成立.则当1+=k n 时,()()()21122122221-->+-⋅=+-+k k k k k . 而当3≥n 时,02)1(2>--k 恒成立.故当1+=k n 时,()2112+>+k k 也成立. 由第一类数学归纳法知:22n n ≥.分析 当3=n 时,2332<.显然上式结论不正确,但是为什么得出正确的结果. 就是在起步时错误.当1=n 时成立,并非正确的选择.正确的证法如下:证 由1=n 时,2112>;当2=n 时,2222=;当3=n 时,2332<.当4=n 时,2442=;当5=n 时,2552>;当6=n 时,2662>.由此可得,当5≥n 时,22n n ≥.当5=n 时,2552>.假设当)5(≥=k k n 时,22k k >成立.则当1+=k n 时,()()()021122122221>-->+-⋅=+-+k k k k k . 故当1+=k n 时,()2112+>+k k 也成立. 由第一类数学归纳法知:22n n ≥.4.2 机械套用数学归纳法的两个步骤致误在用数学归纳法时,一般k n =时推出1+=k n 时成立.当时有时,并非如此,但有时往往不注意.如下:例14 当n 为正奇数时,17+n 能否被8整除？若能,用数学归纳法证明;若不能,请举出反例.错证 当1=n 时,817=+能被8整除,命题成立.假设当k n =时命题成立,即17+k 能被8整除.当1+=k n 时,6)17(7171-+=++k k 不能被8整除.分析 如果1+=k n 时,n 就是所有的正整数，而不是所有的正奇数.故上述是错误的证法.机械套用数学归纳法中的两个步骤致误.证 当1=n 时,817=+能被8整除,命题成立.假设当k n =时命题成立,即17+k 能被8整除.当2+=k n 时,48)17(4971)17(717222-+=-++=++k k k因17+k 能被8整除且48能被8整除,即当2+=k n 时,命题也成立.故当n 为正奇数时,17+n 能被8整除.4.3 混淆概念所致不完全归纳法是从一类对象中部分对象都具有某种性质推出这类对象全体都具有这种性质的归纳推理方法.而有时往往把数学归纳法误认为是数学归纳法导致错误.费马是17世纪法国著名的数学家,他认为,当N n ∈时,n22+1一定都是质数,这是他对0=n ,1,2,3,4作了验证后得到的．因为当0=n ,1,2,3,4时,它的值分别等于3,5,17,257,65537．这五个数都是素数.后来,18世纪伟大的瑞士科学家欧拉证明了641670041742949672971252⨯==+. 从而否定了费马的推测.没想到当5=n 这一结论便不成立.后来,有人还证明了当6=n ,7,8,9时候,式子的值也都不是素数.由此可见,只是验证有限个n ,也就是不完全归纳法,严格按数学归纳法证才能正确.4.4 归纳递推的必要性例15 求证:22221123(1)(21)6n n n n ++++=++.错证 当1n =时,得21112316=⨯⨯⨯=,这时等式成立. 假设n k =时, 这个等式成立；当1n k =+时, 222221123(1)(1)[(1)1][2(1)1]6k k k k k ++++++=+++++ 而11(1)[(1)1][2(1)1](1)(2)(23)66k k k k k k +++++=+++. 所以222221123(1)(1)(2)(23)6k k k k k ++++++=+++. 故当1n k =+时,这个等式也是成立的.归纳步骤完成,结论成立.分析 上面的证明似乎也用到了数学归纳法的两个步骤,但事实上,在证明等式222221123(1)(1)(2)(23)6k k k k k ++++++=+++ 的过程中根本没有用到22221123(1)(21)6k k k k ++++=++这个式子. 即从“k ”到“1k +”的过程.证 当1n =时,得21112316=⨯⨯⨯=,这时等式成立. 假设n k =时, 这个等式成立；在n k =时,这个等式两边都加上2(1)k +,得2222221123(1)(1)(21)(1)6k k k k k k ++++++=+++ 1(1)(2)(23)6k k k =+++ 这就是说, 当1n k =+时, 这个等式是成立的.归纳步骤完成,就可以断定,对于任何自然数n ,这个等式都能成立.上面举的几类错误地应用数学归纳法的例子,实际上通过这些例子说明了应用数学归纳法应当注意的地方.让大家明白数学归纳法的两个步骤是密切联系、缺一不可的.5 总结由上述的论证过程,我们可以看到,在用数学归纳法证明与自然数有关的命题时,两个基本步骤是不可缺少的,否则命题不一定成立.用数学归纳法证明命题可以降低过程的复杂性,使推理过程简单,清晰,也保证了推理的严谨性,特别是在初等数论中的众多命题的证明时,使得证明过程简洁明了,而不失严密性,数学归纳法是一种行之有效的证明方法.尽管数学归纳法是一种证明方法,但实质是递推思想,只要把握住“递推”,巧妙的进行命题转换,以递推分析为主,这样就可以理解其实质,掌握证题技巧,真正提高分析问题解决问题的能力.致谢本论文的完成要特别感谢我的指导老师薛琳为我指导,耐心的帮助我分析问题,理顺思路,使我将书本上的知识加以灵活运用,最终确定了论文的研究思路与研究方向.同时,愿借此机会,感谢洛阳师范学院对我的培养,感谢各位授课老师的辛勤劳动,另外还要感谢同学们互帮互学的情谊,感谢参考文献的作者.这一切是本人完成学业,并取得研究成果的重要前提.感谢各位同学,在平时的学习、本论文写作过程中给予的指导与帮助.参考文献[1]闵嗣鹤.初等数论[J].高等教育出版社,2003.[2]苏淳.漫话数学归纳法[M].中国科学技术大学出版社,2001.[3]吕孝亮.关于数学归纳法的基础研究[J].学术论坛前沿,2008,12(1)：291.[4]华罗庚.数学归纳法[M].科学出版社,2002.[5]洪波.怎样应用数学归纳法[M].上海教育出版社,1979.[6]单樽.初等数论[M].南京大学出版社,2000.[7]邓元春.数学归纳法在数论中的运用举隅[J].江西师范大学数学与信息科学学院,2010,10(1)：47-48.Mathematical Induction and Application in ElementaryNumber TheorySUN Yan-yanCollege of Mathematics Science No：110412016Tutor：XUE LinAbstract:Mathematical induction is a method of mathematical proof which is very important, typically using for determining an expression in the context of all natural numbers is set up or an infinite series is established.This article introduces the mathematical induction by drect proof methods,and descibes two basic steps and principles of mathematical induction.Elementary number theory is the study of the problem of integer,so it is a very important way that applying mathematical induction prove theories of elementary number theory.Key Words:mathematical induction; elementary number theory;integer division; indeterminate equation;congruence。