数学归纳法在竞赛解题中的应用

● (嘉兴市第一中学 浙江嘉兴 314050)

数学归纳法在竞赛解题中的应用

●吕峰波(嘉兴市第一中学 浙江嘉兴 314050)

数学归纳法是证明关于正整数n的命题P(n)的重要方法，是通过有限次的验证、假设和论证来代替无限次(或多次)的验证，从而达到严格证明命题的目的．利用数学归纳法证明命题P(n)的步骤是：

(1)证明:当n取第1个值n0时,P(n)成立；

(2)假设当n=k(k∈N*，且k≥n0)时,P(k)成立，证明:当n=k+1时,P(k+1)也成立．

根据(1)和(2)可知，命题P(n)对一切正整数n都成立．

以上又称第一数学归纳法．数学归纳法还具有多种变形，主要有：

变形1(1)证明命题对n=n0(n0≥1)成立；(2)假设命题在n0≤n≤k(k≥n0)时,P(n)成立，能证明n=k+1时命题也成立．根据(1)和(2)可知，命题对一切正整数n都成立．其又称为第二数学归纳法．

变形2(1)证明命题对n=n0+1，n0+2，…，n0+r成立；(2)假设命题在n=k(k≤n0+r)时成立，能推出n=k+r时命题也成立．根据(1)和(2)可知，命题对一切正整数n都成立．其又称为跳跃数学归纳法．

变形3(1)证明命题对n=n0(n0为一个固定的正整数)成立；(2)假设命题在n=k(2≤k≤n0)时P(n)成立，能证明n=k-1时命题也成立．根据(1)和(2)可知，命题对不超过n0的一切正整数n都成立．其又称为反向数学归纳法．

数学归纳法风格独特，既有固定的程序，又有极大的灵活性和技巧性．下面对数学归纳法的常用技巧作一些探讨．

1 巧妙添项，配凑形式

例1已知n∈N*，求证：11n+2+122n+1能被133整除．

证明(1)当n=1时，

113+123=1 331+1 728=3 059=133×23,

能被133整除，命题成立．

(2)假设当n=k时命题成立，即11k+2+122k+1能被133整除,则

11k+3+122k+3=

11×(11k+2+122k+1)+122k+3-11×122k+1=

11×(11k+2+122k+1)+122k+1×(122-11)=

11×(11k+2+122k+1)+122k+1×133,

能被133整除,即当n=k+1时命题也成立．

根据(1)和(2)，可知命题对n∈N*都成立．

评注在本题中，将11k+2+122k+3变形为

11×(11k+2+122k+1)+122k+3-11×122k+1，

就可以充分运用归纳假设，使问题迎刃而解．

2 大胆尝试，先猜后证

即当n=k+1时,猜想也成立．

根据(1)和(2)，可知对一切自然数n，猜想都成立．于是

3 增多起点，加大跨度

由归纳假设P(k)成立很难导出P(k+1)成立，但能导出P(k+r)(r≥2)成立时，可以加大跨度，使用跳跃数学归纳法，但相应地就要增多起点．

例3设n∈N*，证明：对所有实数x，有

证明(1)当n=0时，左边=|cosx|>0=右边，不等式成立．

|cosx|+|cos2x|=1-2cos2x+|cosx|=

1+|cosx|(1-2|cosx|)≥

此时不等式成立．

左边=|cosx|+(|cos2x|+|cos4x|+…+

|cos2k·2x|)≥

|cosx|+|cos2x|≥1，

因此

左边=(|cosx|+|cos2x|)+(|cos4x|+

…+|cos2k-1·4x|)≥

也就是说当n=k+1时,不等式也成立．

根据(1)和(2)，可知不等式对任何n∈N*都成立．

4 有进有退，反向归纳

例4证明：对于所有正整数n，

证明考虑数列

h=n,n-1,…,1．

下面对h用数学归纳法证明:

(1)当h=n时，不等式成立，即

(2)假设当h=k(k≥2)时，不等式成立，即

则当h=k-1时，

特别地，对h=1，有bn<1+1=2．

评注本题中an和an-1并无简单的递推关系，于是固定了n，转而考虑数列

其中h由n减少到1(虽然bn的下标由1增至n)．

5 合理归纳，选好对象

例5在m×n的格子纸中填入mn个两两不同的数字，用红笔圈出每行最大的s个数，用蓝笔圈出每列最大的t个数，那么至少有st个数同时被红蓝笔圈出．

证明对s+t用数学归纳法．

(1)当s+t=2时，s=t=1，结论成立，因为最大的一个数一定同时被红蓝笔圈出.

(2)假设当s+t=k时结论成立,则当s+t=k+1时，分情况讨论：

①若在某一行中有s个数同时被红蓝笔圈出，则将这行删去，在剩下的表中用黄笔圈出每列中最大的t-1个数(注意：被黄笔圈出的数必已用蓝笔圈出).由归纳假设可知，至少有s(t-1)个数同时被红黄笔圈出．再加上被删去的一行的s个同时被红蓝笔圈出的数，格子纸中同时被红蓝笔圈出的数至少有st个．

②若在某一列中有t个数同时被红蓝笔圈出，则同理可证．

下面证明，情况①和情况②必有一种成立．

把格子纸中所有填数减序排列记为b1,b2,…,bmn，显然b1同时被红蓝笔圈出，记第1个不被红笔和蓝笔圈出的数为br．若br不被红笔圈出，则与br同行的数至少有s个比br大，于是由br的定义可知,这s个数全被红蓝笔圈出;若br不被蓝笔圈出，则与br同列的数至少有t个比br大，于是这t个数全被红蓝笔圈出．

根据(1)和(2)，可知结论成立．

评注对于与正整数s，t有关的命题，常用的思考方法是对s，t或者s+t进行归纳．

6 曲中求伸，强化命题

有些命题P(n)直接用数学归纳法处理时，难以实现从n到n+1的过渡；然而比P(n)更强的命题Q(n)，用数学归纳法证明时反显简单，因此需要对原命题给予加强．

例6已知n∈N*，求证：

证明用数学归纳法证明不等式:

(1)当n=1时，

不等式成立．

(2)假设当n=k时，不等式成立，即

则当n=k+1时，

即当n=k+1时不等式也成立．

根据(1)和(2)，可知不等式对任何n∈N*都成立．

7 欲擒故纵，推广命题

对仅与某些较大的正整数有关的命题，可以考虑把它推广到任意正整数n，再用数学归纳法证明推广后的命题．这种“欲擒故纵”的解题策略也可以解决数学竞赛中的许多问题．

证明用数学归纳法证明:对n≥1，有不等式

(1)当n=1时，x2≥3x1>x1=a．

(2)假设不等式对不大于k的数都成立，则

更进一步，由x1>0，得x2,x3,…,xk>0，于是

xk+2>(k+1)xk+1>(k+1)(a·k!)．

根据(1)和(2)，可知

于是，对足够大的n，有xn+1>a·n!>2 010!．

8 孪生命题，螺旋归纳

在命题论证中，有时会出现一个命题的2个部分“跷跷板式连环相套”的现象．对付这种现象的一种办法就是：将原来对一个命题的证明，变为跷跷板归纳式的同时证明一对孪生命题．这种归纳证明的方法也称为螺旋归纳法．

例8证明:在斐波那契数列中，有

(1)当n=1时，在P(n)中，

在Q(n)中，

因此等式P(n)和Q(n)都成立．

F2k+1+F2k+2=F2k+3,

F2k+2+F2k+3=F2k+4.

也就是说当n=k+1时,等式P(n)和Q(n)都成立．

根据(1)和(2)，可知等式P(n)和Q(n)对任何n∈N*都成立．

9 弱化命题，以退求进

数学归纳法的另外一种命题转化形式是:先证一个比原命题弱的命题；然后以此为基础，再去证明原命题．弱化命题能起到减弱证明难度、分散证明难点，实现以退求进的作用．

例9函数f(x)是定义在正整数上且取值为正整数的函数，有f(n+1)>f(f(n))，证明：对一切正整数n，都有f(n)=n．

证明先用数学归纳法证明一个较弱的命题：已知m,n∈N*，若m≥n，则

(1)当n=1时，对一切正整数m≥1，都有f(m)≥1，因此式(1)成立．

(2)假设当n=k时，式(1)成立.即若m≥k，则f(m)≥k，m,k∈N*．从而当m≥k+1时，由m-1≥k，得

f(m-1)≥k.

又由f(m-1)∈N*，得

f(f(m-1))≥k，

于是

f(m)>f(f(m-1))≥k．

又因为f(m)∈N*，所以f(m)≥k+1，也就是说当n=k+1时,式(1)也成立．

根据(1)和(2)，可知式(1)对任何m≥n(m,n∈N*)都成立．

令m=n，即f(n)≥n，则

f(n)≤f(f(n))

于是函数f(x)在正整数集上单调递增，从而

n≤f(n)

又因为f(n)∈N*，所以f(n)=n．

评注本题中的条件以不等式的形式给出，而结论以等式的面目给出，难以一步证明成功，因此考虑弱化命题．

[1] 苏淳.漫话数学归纳法的应用技巧[M].合肥:中国科学技术大学出版社，1992.