数学归纳法以及其在初等数论中的应用

LUOYANG NORMAL UNIVERSITY

2013届 本科毕业论文

数学归纳法及其在初等数论中的应用

院（系）名称

专 业 名 称

学

学

指导教生姓名 号 师 数学科学学院 数学与应用数学 孙xx 110412016 xx 讲师

2013.5 完 成 时 间

数学归纳法及其在初等数论的应用

孙xx

数学科学学院 数学与应用数学 学号：110412016

指导教师：xx

摘 要：数学归纳法是一种非常重要的数学证明方法, 典型的用于确定一个表达式在所有自然数范围内是成立的或者用于确定一个其他形式在一个无穷数列是成立的. 本文通过直接证法引入数学归纳法, 并介绍了数学归纳法的两个基本步骤及原理. 初等数论研究的是关于整数的问题, 故应用数学归纳法证明初等数论中的有关的命题是重要的途径.

关键词：数学归纳法; 初等数论; 不定方程; 整除; 同余

1 引论

1.1 直接证法

众所周知, 数学上的许多命题都与自然数有关. 这里所指的n , 往往是指任意的一个自然数. 因此, 这样的一个命题实际上也就是一个整列命题. 要证明这样一整列命题成立, 当然可以有多种不同的方法.

其中常用的方法是置n 的任何具体值而不顾, 而把它看成是一个任意的自然数, 也就是说, 假定它只是任何自然数都具备的共同性质, 并且在这样的基础上进行推导、运算. 如果我们在推导运算中没有遇到什么难以克服的困难, 那么我们就有可能用这种方法来完成命题的证明了. 这种方法就是习惯上所说的直接证法. 如下例：

例1 已知x i ∈R （i =1, 2, ⋅⋅⋅, n ; n ≥2）, 满足

x 1+x 2+ +x n =1, x 1+x 2+ +x n =0.

证明

x 1+x x 211+ +n ≤-. 2n 22n

证 由条件x 1+x 2+ +x n =1知x 1, x 2, , x n 不全为零;

由条件x 1+x 2+ +x n =0知这n 个实数中既有正数也有负数. 记

A 1={i :x i ≥0}, A 2={i :x i

则A 1和A 2都不是空集, 它们互不相交, 且A 1⋃A 2={1,2,3, , n }.

若再记S 1=∑x i , S 2=∑x i , 就有

i ∈A 1i ∈A 2

S 1+S 2=0,S 1-S 2=1.

因此知S 1=-S 2=1. 采用所引入的符号, 就有 2

x 1+x 2x + +n =2n i ∈A 1∑i +∑i i ∈A 2x i x i .

由A 1和A 2的定义和性质知∑

有 ∑i =1n i ∈A 1x i x 是若干非负数之和, ∑i 是若干负数之和, 因此就i i ∈A 2i x i =i x i x i +≤∑∑i i i ∈A 1i ∈A 2i ∈A 2∑x i +1∑x i n i ∈A 2

=S 1+可见命题的结论是成立的. S 21111=-=-. n 22n 22n

在这个证明中, 我们没有考虑n 究竟是几的问题, 只是把精力花费在对命题条件的推敲和剖析上. 这种证法就是直接证法．

1.2 数学归纳法

有时, 我们也会碰到一些与n 有关的命题, 对于它们很难从任意的n 入手, 那么我们就只能另辟蹊径, 也就是所谓的数学归纳法. 如下例：

例2 证明对于每个不小于3的自然数n , 都可以找到一个正整数a n , 使它可以表示为自身的n 个互不相同的正约数之和．

分析 显然, 我们很难对任意一个不小于3的自然数n , 直接去找到出相应的a n 来. 面对这样的情形, 较为稳妥的做法只能是先从a 3, a 4, 找起. 经过不多的几

步探索, 就可以发现, 有

6=1+2+3.

而且1, 2, 3恰好是6的3个互不相同的正约数, 因此可将a 3取作6. 在此基础上, 又可发现有

12=1+2+3+6.

而且1, 2, 3, 6恰好又是12的4个互不相同的正约数, 因此又可取a 4=12．循环下去, 便知可依次取24, 48, ．这也就告诉我们：如果取定了a k , 那么接下去就只要再取a k +1=2a k 就行了.

证 当n =3时, 6=1+2+3.

假设当n =k 时成立, 即a k 可以表示成自身的k 个互不相同的正约数

b 1

之和, 即

a k =b 1+b 2+ +b k .

取定a k +1=2a k , 则：

a k +1=b 1+b 2+ +b k +a k .

若记b k +1=a k , 则显然有b 1

由上所述, 数学归纳法可以处理像例2那样不宜于采用直接证法的问题, 也可以处理一些可以通过直接证法来解决的问题. 如下例:

例3 证明:对任何自然数n , 数5n +2⋅3n -1+1能被8整除.

若用直接证法, 则如下：

证 按照n 的奇偶性, 可以将上式表示两种不同的形式.

当n 为奇数时, 有

(5

当n 为偶数时, 有 n +3n )-(3n -1-1).

5(5n -1+3n -1)-(3n -1).

于是上述两式中, 第一个括号内的指数都是奇数, 第二个括号内的指数都是偶数. 而当k 为奇数, 则有

a k +b k =(a +b )(a k -1-a k -2b + +b k -1) .

当k 为偶数, 则c 2-1可整除c k -1.

当a =5, b =3, c =3, 可根据上式得出两式是8的倍数. 从而命题得证.

若用数学归纳法, 则如下：

证 当n =1时, 5n +2⋅3n -1+1=8能被8整除.

假设n =k 时, A k 能被8整除.

则当n =k +1时, 我们有

A k +1=5k +1+2⋅3k +1=5⋅5k +6⋅3k -1+1.

所以就有

A k +1-A k =4(5k +3k -1) .

由于对任何自然数k , 数5k 和3k -1都是奇数, 所以其和5k +3k -1恒为偶数. 从而4(5k +3k -1) 一定是8的整数. 即A k +1=A k +4(5k +3k -1) 可被8整除.

由第一类数学归纳法, 对任何自然数n , 数A n 都可被8整除.

1.3 初等数论

初等数论是数的规律, 特别是整数性质的数学分支, 它是数论中的最古老的分支. 其它的组合数论、解析数论、代数数论、几何数论、超越数论都是在初等数论的基础发展起来的.

初等数论是一门十分重要的数学基础课, 小学阶段就有初等数论的影子. 初等数论不仅是师范院校数学专业, 大学数学各专业的必修课, 也是计算科学, 密码学等许多相关专业所需的课程.

2 数学归纳法的原理

2.1 第一类数学归纳法

定理1 设p (n ) 是关于自然数n 的命题, 如果p (n ) 满足:(1)p (n 0) 成立;(2)假设当n =k 时, 命题p (k ) 成立, 可以推出p (k +1) 成立, 则命题p (n ) 对一切自然数n 都成立.

证 假设命题p (n ) 仍不能对一切自然数n ≥n 0成立, 那么如果记

A 1={n :n ≥n 0，p (n ) 不成立}.

A 2={n :n ≥n 0，p (n ) 成立}.

则有A 1≠Φ. 但因已证p (n 0) 成立, 知n 0∉A 1, 即有n 0∈A 2.

由于A 1是非空的自然数集合, 所以由自然数的最小数原理, A 1有最小数n 1. 由于n 0∉A 1, 所以n 1>n 0, 即有n 1-1≥n 0.

由于n 1是A 1中最小的数, 所以n 1-1∉A 1, 从而n 1-1∈A 2.

故当n =n 1-1时p (n ) 成立.

记k =n 1-1, 则由条件(2)知k +1=n 1时p (n 1) 成立, 则与n 1∈A 1矛盾. 故A 1为空集. 也就是说, 有p (n ) 对一切自然数n 都成立.

例4 设S k =1+3n +5n + +(2k -1), n ≡0mod 2, k ∈N *, 试证： n

k >1时, 2k -1S k .

证 当k =1时, 结论显然成立.

假设n =k -1时结论成立, 即当S k -1=1+3n +5n + +(2k -1-1), n ≡0mod 2, k >1n

时,

2k -2S k -1.

现证等于k 时结论成立.

由于

S k -S k -1=2k -1+1+2k -1+3+ +2k -1 ()(n )n ()n

(

≡(-1)[(2n =2k -2k -1-1+2k -2k -1-3k -1[)][n (-1) n +(2k -1-3) n )]+ +(2+ +1] n k -1 )n

又因n ≡0mod 2，故上式：

≡S k -1mod 2k .

即S k ≡2S k -1mod 2k , 但2k -2S k -1, 故推得2k -1S k .

由第一数学归纳法知, 命题对一切正整数k 都成立.

2.2 第二类数学归纳法

定理2 设p (n ) 是关于自然n 的命题, 如果p (n ) 满足:(1)p (1) 成立;(2)假设p (n ) 对于所有满足a

证 设M ={n |p (n )成立，n ∈N }, 又设A =N -M , 假设A 不空,

由自然数的最小数原理, A 有最小数a 0,

又由条件(1)1∈M , 故a 0≠1, 因此

1, 2, , a 0-1∈M .

又由条件(2)知a 0∈M , 这与a 0∈A 矛盾,

故A 为空集, 从而M =N , 则命题p (n ) 对一切自然数n 都成立.

例5 设数列p 1, p 2, , p n , 是由小到大的顺序排列的素数序列. 试证p n

假设当１≤n ≤k 时, 命题成立. 即

2p 1

则有

p 1p 2 p k

所以 21222k

p 1p 2 p k +1≤22+212+ +2k =22k +1-2

k +1k +1上式左边p 1p 2„p k +1本身即小于22, 其素因数当然更小于22, 但它的素

因数不可能为p 1, p 2, „, p k , 所以它的素因数必大于或等于p k +1, 因此有p k +1

2.3 跳跃数学归纳法

定理3 设p (n ) 是一个表示与正整数n 有关的命题, 如果p (n ) 满足(1)当n =1, 2时, p (1) 和p (2) 都成立;(2)假设当n =k 时, 命题p (k ) 成立, 则当n =k +2时, 命题p (k +2) 也成立, 那么p (n ) 对于一切自然数n 都成立. k +1k +1

证 (用反证法) 设p (n ) 不是对所有自然数都成立, 那么使p (n ) 不成立的自然数集为

M ={n |p (n )不成立，n ∈N },

根据最小数原理, M 中一定存在一个最小的自然数k .

由条件(1)可知k ≠1和k ≠2于是k >2, 令k =k 1+2, 则k 1满足p (k 1) 成立. 由条件(2)可知p (k 1) 成立, 则p (k 1+2) 也成立, 即p (k ) 成立. 此与假设p (k ) 不成立相矛盾.

故p (n ) 必对一切自然数n 都成立.

上述结论可以推广到一般情形, 即:

设p (n ) 是一个表示与正整数n 有关的命题, t 为某一自然数(t ≥2). 如果(1)当n =1, 2, , t 时, 命题p (1) , p (2) , , p (t ) 都成立;(2)假设当n =k 时, 命题p (t ) 成立，则当时n =k +t 命题p (k +t ) 也成立, 那么命题p (n ) 对一切的自然数n 都成立.

n 例6 证明对一切自然数n , 都存在自然数x n 和y n 使得x n +y n =1993. 22

证 当n =1时, 取x 1=43, y 1=12即可, 因此

432+122=1849+144=1993.

当n =2时, 注意到432+122=1993, 因此只要令

x 2=432-122=1705, y 2=2⋅43⋅12=1032,

那么就有

x 2+y 2=17052+10322=19932.

故当n =1, n =2也成立.

k 假设当n =k 时存在自然数x k 和y k , 使得x k +y k =1993, 2222

那么显然就有

k +2, (1993x k ) 2+(1993y k ) 2=1993

可取x k +2=1993x k , y k +2=1993y k .

即只要n =k 时断言成立, 即可推得n =k +2断言也成立．

综上所述, 知对一切自然数n 断言都成立.

2.4 反向数学归纳法

定理4 设p (n ) 表示一个与自然数有关n 的命题, 若(1)p (n ) 对无数多个自然数n 都成立;(2)假设p (k ) 成立, 可推出p (k -1) 也成立; 那么p (n ) 对一切自然数n 都成立.

证 (用反证法) 设所有使命题p (n ) 成立的自然数集合为A ，所有使命题p (n ) 不成立的自然数集合为B . 如果B 不是空集, 可在B 中任取一个数b 0, 因A 时无穷集，所以在A 中总能可以找到一个数a 0>b 0.

所以由条件(2),p (a 0) 为真可得p (a 0-1) 为真又得p (a 0-1-1) 为真等等, 经过

有限步之后, 总可使p (b 0) 也为真, 这与假设矛盾，即B 是空集，故命题p (n ) 对所有的自然数n 都成立.

例7 设p 是素数, 而正整数m 与p 互素, 试证:m p -1≡1mod p .

证 问题等价与要证:如果p 是素数, 那么对任意正整数m , 有m p ≡m mod p . 令m =Lp L ∈N *, 则(Lp )≡Lp mod p , 即有无穷多个正整数Lp L ∈N *使得 p ()()

m p ≡m mod p ,

假设m =k +1时, (k +1)≡(k +1)mod p . 则由 p

2p -2p -1(k +1)p =k p +C p k + +C p k +1,

p (p -1) (p -i +1)≡0mod p (1≤i ≤p -1) , i !

知

k +1≡(k +1)≡k p +1mod p . p

故k ≡k p mod p .

从而根据反向归纳法, 对任意正整数m , 有m p ≡m mod p .

2.5 二重数学归纳法

定理5 设p (i , j ) 为与自然数i 和j 相关联的命题函数. 如果(1)当i =i 0, j =j 0时, 命题p (i 0, j 0) 成立.(2)对任一k ≥i 0, 任一l ≥j 0, 假定p (k , l ) 成立, 则p (k +1, l ) 和p (k , l +1) 都成立, 那么p (i , j ) 对一切的i ≥i 0和j ≥j 0都成立.

证 i , j 两次运用第二数学归纳法.

当i =i 0时, 命题p (i 0, j )对j ≥j 0都成立.

事实上, 由条件(1),有j =j 0时p (i 0, j 0) 成立.

由条件(2),假设对任意l ≥j 0, p (i 0, j )成立, 则p (i 0, j +1)也成立.

由第二数学归纳法, 命题p (i 0, j )对任意j ≥j 0都成立.

假设对任一k ≥i 0, 命题p (k , j )对j ≥j 0时成立, p (k +1, j ) 对j ≥j 0也成立. 事实上, 由条件(2),对任意的k ≥i 0, j ≥j 0, 假定p (k , j )成立则p (k +1, j ) 也成立. 根据第二数学归纳法，命题p (k +1, j ) 对一切i ≥i 0和j ≥j 0都成立. 证毕.

例8 试证2mn >m n (m , n 为自然数) .

证 设p (m , n ) 是与自然数m , n 相关的命题函数.

当m =n =1, 有21>11, 显然p (1, 1) .

假设对任一k ≥1, l ≥1, p (k , l ) 为真, 即2kl >k l 成立.

下面证明p (k +1, l ) 和p (k , l +1) 都成立.

2(k +1)l =2kl +l =2⋅2kl >k l ⋅2l ≥(2k )≥(k +1). l l

即有p (k +1, l ) 成立.

2k (l +1)=2kl +k =2kl ⋅2k >k l ⋅2k >k l ⋅k ≥k l +1.

即有p (k , l +1) 成立.

由二重归纳法可知, 对任意的m ≥1, n ≥1, 2mn >m n (m , n 为自然数) .

2.6 第一类数学归纳法和第二类数学归纳法之间的关系

定理6 第一类数学归纳法和第二类数学归纳法等价.

证 假设性质p (n ) 在n =1时成立.

则可以转化为：“由数学归纳法及其应用, 假设当n =k 时, 命题p (k ) 成立, 则可以推出p (k +1) 成立”的充分必要条件为“由p (n ) （其中n ≤k ）成立, 可以推出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 0) 成立推不出p (k 0+1) 成立的所有自然数k 0构成一非空子集, 记m 为该子集的最小自然数.

所以, 对任一自然数n , 只要n

已知p (1) 成立, 因此p (1) 、p (2) 、„、p (m ) 都成立, 然而由此可知p (m +1) 成立, 所以从p (m ) 成立推出了p (m +1) 成立；

另一方面, 由m 的选取可知, 由p (m ) 成立推不出p (m +1) 成立, 这就导出矛盾, 得证.

3 数学归纳法原理在初等数论中的应用

初等数论是研究整数性质的一门理论, 大致分为整数理论、整除理论、同余理

论、不定方程, 而数学归纳法就是关于解决自然数的数学方法, 故初等数论的多数定理, 习题都是通过数学归纳法证明, 例如最基本的算术基本定理就是用第二数学归纳法证明.

3.1 整除性

整除性理论是初等数论的基础. 利用数学归纳法解决初等数论中有关整除问题, 可以解决众多问题.

例9 设集合(a 1, a 2, , a n )为n 元正整数集n ∈N , n =2. 证明

1≤l

1≤l

证 当n =2时, l =1, k =2. 易证结论成立.

假设命题对于n -1(n ≥3) 的情形成立. 即对任意n -1元整数集合(a 1, a 2, , a k -1), 满足 1≤l

11≤l

1≤l

集(a 1, a 2, , a n )中存在一个整数(不妨记为a n ) 使得

p i i (a n -a 1)(a n -a 2) (a n -a n -1) .

⎛⎫'若p i ()k -l ⎪ ∏⎪=r i , 则由归纳假设, 得 ⎝1≤l

⎛⎫()p i a -a l ⎪ ∏k ⎪. ⎝1≤l

即可得：

p i r i +r i '

1≤l

因为

αi =p i ⎛

⎝1≤l

⎛⎫ =p i ()()n -1! a -a ∏k l ⎪ ⎪

1≤l

⎛⎫()=p i ((n -1)! )p i a -a l ⎪ ∏k ⎪ ⎝1≤l

'=r i +r i .

所以

p r i +r i '

1≤l

又因p 1α1, p 2α2, , p l αl 两两互质, 所以

p 11p 22 p l αααl

1≤l

又

故 1≤l

1≤l

由第一类数学归纳法结论成立.

例10 证明存在正整数m , 使得f (n )=(2n +7)⋅3n +9对任意自然数n 都能被m 整除? 若存在, 求出最大的m 值, 并证明你的结论.

证 当n =1时有f (1)=(2+7)⋅3+9=36,

当n =2时有f (2)=(4+7)⋅32+9=108=3⨯36,

当n =3时有f (3)=(6+7)⋅33+9=360=10⨯36,

由此推想存在正整数m , 且m 的最大值为36, 即对任意的自然数n ，f (n ) 都能被36整除.

当n =1时明显有命题成立；

假设当n =k 时有命题成立, 即f (k )=(2k +7)⋅3k +9能被36整除.

那么当n =k +1时有

f (k +1)=[2(k +1)+7]⋅3k +1+9

=3(2k +7)⋅3k +3⋅9+3⋅2⋅3k -18

=3(2k +7)⋅3k +3⋅9+183k -1-1.

由于3k -1-1(k ≥2)是2的倍数, 故有18(3k -1-1)是36的倍数. ()

即18(3k -1-1)能被36整除, 由假设得f (k +1)能被36整除.

即命题成立, 故存在最大的正整数m , 且m 的值为36.

3.2 不定方程

不定方程是指未知数的个数多于方程的个数的式子, 是数论的一个分支, 它有着悠久的历史与丰富的内容. 早在公元3世纪古希腊的丢番图就开始研究不定方程. 著名费马大定理, 就是关于不定方程的问题. 他在阅读丢番图《算术》时写到:将一个立方数分成两个立方数之和, 或一个四次幂分成两个四次幂之和, 或者一般地将一个高于二次的幂分成两个同次幂之和, 这是不可能的. 关于此, 我确信已发现了一种美妙的证法 , 可惜这里空白的地方太小, 写不下. 也就是:

当n ≥3时, 不定方程

x n +y n =z n

没有正整数解.

这个问题困扰了数学家几百年, 至到英国数学家安德鲁⋅怀尔斯的出现. 可见, 不定方程是数论的重要一部分.

不定方程一般要解决三个问题:一是判断何时有解, 二是决定解的个数, 三是求出所有的解. 我们就可以利用数学归纳法解决问题. 如下例:

例11 证明对一切自然数n , 不定方程x 2+y 2=z n 都有正整数解.

证 当n =1时, 取x =y =1, z =2.

当n =2, 取x =3, y =4, z =5.

即满足方程, 故知命题n =1和2时成立.

假定当n =k 时, x =x 0, y =y 0, z =z 0是方程的一组正数解; 那么当n =k +2, 只要取x =x 0z 0, y =y 0z 0, z =z 0, 则有

(x 0z 0)2+(y 0z 0)2=z 02(x 02+z 02)=z 0k +2.

知它们恰为方程的一组正整数解, 所以当n =k +2时, 命题成立.

由于采用了两个起点, 所以可以用两个跳跃, 这表明对一切自然数n , 不定方程都有正整数解, 证毕.

3.3同余

在日常生活中, 我们所要注意的常常不是某些整数, 而是这些数用某一固定的

数去除所得的余数. 例如问现在是星期几, 就是问用7去除某一个总的天数所得的余数. 这样, 就在数学中产生了同余概念. 同余理论是初等数论的重要组成部分, 是研究整数问题的重要工具之一, 利用同余来论证某些整除性的问题是很简便的. 同样, 我们可以数学归纳法来研究同余问题. 如下所示:

例12 已知a 1=1, a 2=2, 而当n ≥3时有

⎧5a n -1-3a n -2, 若a n -1⋅a n -2为偶数, a n =⎨⎩a n -1-a n -2, 若a n -1⋅a n -2为奇数

证明对一切自然数n , 都有a n ≠0.

分析 在这里显然有a 1≠0, a 2≠0. 但若假设a k -1≠0, a k ≠0, 却很难有所给的递推关系式断言a k +1≠0. 可见就原命题证明原命题也很难奏效.

我们可以多演算几项, 最初的一些项依次是：1,2,7,29,22,23,49,26, . 它们显然都是不为零, 不过其中既有奇数, 也有偶数. 但是, 我们求同余, 可以得出依次是被4除的余数是1,2,3,1,2,3, , 有着非常明显的规律. 这就启发我们猜测, 可能对一切n , 都会有

a 3n -2≡1mod 4, a 3n -1≡2mod 4, a 3n ≡3mod 4.

如果这一猜测真能成立, 那么数列中的一切项当然也就不可能成为零了.

证 显然a 1≡1mod 4, a 2≡2mod 4, a 3≡3mod 4,

故在n =1时成立.

假设当n =k 时, 我们的猜测也成立, 即有：

a 3k -2≡1mod 4, a 3k -1≡2mod 4, a 3k ≡3mod 4.

那么当n =k +1时, 由递推公式可知

a 3k +1≡5a 3k -3a 3k -1≡15-6≡9≡1mod 4；

a 3k +2≡a 3k +1-a 3k ≡1-3≡-2≡2mod 4；

a 3k +3≡5a 3k +2-3a 3k +1≡10-3≡7≡3mod 4.

这就表明, 当n =k +1时, 我们的猜测也正确.

故知对一切n , a n ≠0.

3.4 初等数论中的不等式

例13 若x 是一个正实数, n 是一个正整数, 证明：

[nx ]≥[x ]+[2x ]+[3x ]+ +[nx ]. 123n

证 设x k =[x ]+[2x ]+[3x ]+ +[kx ], 则123k x k =x k -1+[kx ].

k

当n =1时, 显然有[x ]≥x 1=[x ].

1

假设不等式n ≤k -1时都成立, 即x i ≤[ix ](i =1, 2, , k -1).

考虑n =k 时的情形. 由于

kx k =(k -1)x k -1+x k -1+[kx ],

(k -1)x k -1=(k -2)x k -2+x k -2+[(k -1)x ],

3x 3=2x 2+x 2+[3x ],

2x 2=x 1+x 1+[2x ],

将以上各式两边分别相加, 得

kx k =x k -1+x k -2+ +x 2+x 1+x 1+[kx ]+ +[3x ]+[2x ],

由归纳假设, x i ≤[ix ](i =1, 2, , k -1), 则

kx k ≤[(k -1)x ]+[(k -2)x ]+ +[2x ]+[x ]+[x ]+[kx ]+ +[3x ]+[2x ]

=([(k -1)x ]+[x ])+([(k -2)x ]+[2x ])+ +([x ]+[(k -1)x ])+[kx ].

由[a ]+[b ]≤[a +b ], 则

kx k ≤[kx ]+[kx ]+ +[kx ]=k [kx ].

故x k ≤[kx ].

即n =k 时不等式成立, 从而对任意的自然数n , 都有

[nx ]≥[x ]+[2x ]+[3x ]+ +[nx ]. 123n

4 数学归纳法在初等数论中注意的问题

数学归纳法的两个步骤中, 我们通常将验证p (n 0) 成立称作起步; 将假设条件成为归纳假设, 而将由归纳假设推出p (k +1) 也成立的过程叫做归纳过渡. 这几步缺一不可. 如果使用不当就可能导致错误.

4.1 起步错误

在数学归纳法的基本形式之下, 第一步通常总是由验证p (n 0) 成立开始, 但是往往容易忽略, 觉得无关紧要, 可有可无, 不去认真的验证这一步, 或者根本没有这一步, 都可能陷入错误之中, 推出看似正确的答案. 如下例：

例14 试讨论2n 与n 2的大小.

错解 由n =1时, 21>12; n =2时, 22=22.

假设当n =k 时, 2k >k 2成立.

则当n =k +1时,

2k +1-(k +1)=2⋅2k -(k +1)>(k -1)-2. 222

而当n ≥3时, (k -1) 2-2>0恒成立.

故当n =k +1时, 2k +1>(k +1)也成立. 2

由第一类数学归纳法知:2n ≥n 2.

分析 当n =3时, 23

证 由n =1时, 21>12; 当n =2时, 22=22; 当n =3时, 23

当n =4时, 24=42; 当n =5时, 25>52; 当n =6时, 26>62.

由此可得, 当n ≥5时, 2n ≥n 2.

当n =5时, 25>52.

假设当n =k (k ≥5) 时, 2k >k 2成立.

则当n =k +1时,

2k +1-(k +1)=2⋅2k -(k +1)>(k -1)-2>0. 222

故当n =k +1时, 2k +1>(k +1)也成立. 2

由第一类数学归纳法知:2n ≥n 2.

4.2 机械套用数学归纳法的两个步骤致误

在用数学归纳法时, 一般n =k 时推出n =k +1时成立. 当时有时, 并非如此, 但有时往往不注意. 如下:

例14 当n 为正奇数时, 7n +1能否被8整除？若能, 用数学归纳法证明; 若不能, 请举出反例.

错证 当n =1时, 7+1=8能被8整除, 命题成立.

假设当n =k 时命题成立, 即7k +1能被8整除.

当n =k +1时, 7k +1+1=7(7k +1) -6不能被8整除.

分析 如果n =k +1时, n 就是所有的正整数，而不是所有的正奇数. 故上述是错误的证法. 机械套用数学归纳法中的两个步骤致误.

证 当n =1时, 7+1=8能被8整除, 命题成立.

假设当n =k 时命题成立, 即7k +1能被8整除.

当n =k +2时,

7k +2+1=72(7k +1) +1-72=49(7k +1) -48

因7k +1能被8整除且48能被8整除, 即当n =k +2时, 命题也成立.

故当n 为正奇数时, 7n +1能被8整除.

4.3 混淆概念所致

不完全归纳法是从一类对象中部分对象都具有某种性质推出这类对象全体都具有这种性质的归纳推理方法. 而有时往往把数学归纳法误认为是数学归纳法导致错误.

费马是17世纪法国著名的数学家, 他认为, 当n ∈N 时, 2+1一定都是质数, 这是他对n =0, 1, 2, 3, 4作了验证后得到的．

因为当n =0, 1, 2, 3, 4时, 它的值分别等于3, 5, 17, 257, 65537．

这五个数都是素数. 后来,18世纪伟大的瑞士科学家欧拉证明了 2n

22+1=4294967297=6700417⨯641.

从而否定了费马的推测. 没想到当n =5这一结论便不成立. 后来, 有人还证明了当n =6, 7, 8, 9时候, 式子的值也都不是素数. 由此可见, 只是验证有限个n , 也就是不完全归纳法, 严格按数学归纳法证才能正确.

4.4 归纳递推的必要性

例15 求证:12+22+32+ +n 2=1n (n +1)(2n +1) . 65

1错证 当n =1时, 得12=⨯1⨯2⨯3=1, 这时等式成立. 6

假设n =k 时, 这个等式成立；

1当n =k +1时, 12+22+32+ +k 2+(k +1) 2=(k +1)[(k +1) +1][2(k +1) +1] 6

而

11(k +1)[(k +1) +1][2(k +1) +1]=(k +1)(k +2)(2k +3) . 66

所以

112+22+32+ +k 2+(k +1) 2=(k +1)(k +2)(2k +3) . 6

故当n =k +1时, 这个等式也是成立的.

归纳步骤完成, 结论成立.

分析 上面的证明似乎也用到了数学归纳法的两个步骤, 但事实上, 在证明等式

112+22+32+ +k 2+(k +1) 2=(k +1)(k +2)(2k +3) 6

的过程中根本没有用到12+22+32+ +k 2=

即从“k ”到“k +1”的过程. 1k (k +1)(2k +1) 这个式子. 6

1证 当n =1时, 得12=⨯1⨯2⨯3=1, 这时等式成立. 6

假设n =k 时, 这个等式成立；

在n =k 时, 这个等式两边都加上(k +1) 2, 得

12+22+32+ +k 2+(k +1) 2=1k (k +1)(2k +1)(k +1) 2 6

1(k +1)(k +2)(2k +3) 6 =

这就是说, 当n =k +1时, 这个等式是成立的.

归纳步骤完成, 就可以断定, 对于任何自然数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 Elementary

Number Theory

SUN Yan-yan

College of Mathematics Science No：110412016

Tutor ：XUE Lin

Abstract: 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