● (嘉興市第一中學(xué) 浙江嘉興 314050)

數(shù)學(xué)歸納法在競(jìng)賽解題中的應(yīng)用

●呂峰波(嘉興市第一中學(xué) 浙江嘉興 314050)

數(shù)學(xué)歸納法是證明關(guān)于正整數(shù)n的命題P(n)的重要方法，是通過(guò)有限次的驗(yàn)證、假設(shè)和論證來(lái)代替無(wú)限次(或多次)的驗(yàn)證，從而達(dá)到嚴(yán)格證明命題的目的．利用數(shù)學(xué)歸納法證明命題P(n)的步驟是：

(1)證明:當(dāng)n取第1個(gè)值n0時(shí),P(n)成立；

(2)假設(shè)當(dāng)n=k(k∈N*，且k≥n0)時(shí),P(k)成立，證明:當(dāng)n=k+1時(shí),P(k+1)也成立．

根據(jù)(1)和(2)可知，命題P(n)對(duì)一切正整數(shù)n都成立．

以上又稱第一數(shù)學(xué)歸納法．?dāng)?shù)學(xué)歸納法還具有多種變形，主要有：

變形1(1)證明命題對(duì)n=n0(n0≥1)成立；(2)假設(shè)命題在n0≤n≤k(k≥n0)時(shí),P(n)成立，能證明n=k+1時(shí)命題也成立．根據(jù)(1)和(2)可知，命題對(duì)一切正整數(shù)n都成立．其又稱為第二數(shù)學(xué)歸納法．

變形2(1)證明命題對(duì)n=n0+1，n0+2，…，n0+r成立；(2)假設(shè)命題在n=k(k≤n0+r)時(shí)成立，能推出n=k+r時(shí)命題也成立．根據(jù)(1)和(2)可知，命題對(duì)一切正整數(shù)n都成立．其又稱為跳躍數(shù)學(xué)歸納法．

變形3(1)證明命題對(duì)n=n0(n0為一個(gè)固定的正整數(shù))成立；(2)假設(shè)命題在n=k(2≤k≤n0)時(shí)P(n)成立，能證明n=k-1時(shí)命題也成立．根據(jù)(1)和(2)可知，命題對(duì)不超過(guò)n0的一切正整數(shù)n都成立．其又稱為反向數(shù)學(xué)歸納法．

數(shù)學(xué)歸納法風(fēng)格獨(dú)特，既有固定的程序，又有極大的靈活性和技巧性．下面對(duì)數(shù)學(xué)歸納法的常用技巧作一些探討．

1 巧妙添項(xiàng)，配湊形式

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

證明(1)當(dāng)n=1時(shí)，

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

能被133整除，命題成立．

(2)假設(shè)當(dāng)n=k時(shí)命題成立，即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整除,即當(dāng)n=k+1時(shí)命題也成立．

根據(jù)(1)和(2)，可知命題對(duì)n∈N*都成立．

評(píng)注在本題中，將11k+2+122k+3變形為

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

就可以充分運(yùn)用歸納假設(shè)，使問(wèn)題迎刃而解．

2 大膽嘗試，先猜后證

即當(dāng)n=k+1時(shí),猜想也成立．

根據(jù)(1)和(2)，可知對(duì)一切自然數(shù)n，猜想都成立．于是

3 增多起點(diǎn)，加大跨度

由歸納假設(shè)P(k)成立很難導(dǎo)出P(k+1)成立，但能導(dǎo)出P(k+r)(r≥2)成立時(shí)，可以加大跨度，使用跳躍數(shù)學(xué)歸納法，但相應(yīng)地就要增多起點(diǎn)．

例3設(shè)n∈N*，證明：對(duì)所有實(shí)數(shù)x，有

證明(1)當(dāng)n=0時(shí)，左邊=|cosx|>0=右邊，不等式成立．

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

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

此時(shí)不等式成立．

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

|cos2k·2x|)≥

|cosx|+|cos2x|≥1，

因此

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

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

也就是說(shuō)當(dāng)n=k+1時(shí),不等式也成立．

根據(jù)(1)和(2)，可知不等式對(duì)任何n∈N*都成立．

4 有進(jìn)有退，反向歸納

例4證明：對(duì)于所有正整數(shù)n，

證明考慮數(shù)列

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

下面對(duì)h用數(shù)學(xué)歸納法證明:

(1)當(dāng)h=n時(shí)，不等式成立，即

(2)假設(shè)當(dāng)h=k(k≥2)時(shí)，不等式成立，即

則當(dāng)h=k-1時(shí)，

特別地，對(duì)h=1，有bn<1+1=2．

評(píng)注本題中an和an-1并無(wú)簡(jiǎn)單的遞推關(guān)系，于是固定了n，轉(zhuǎn)而考慮數(shù)列

其中h由n減少到1(雖然bn的下標(biāo)由1增至n)．

5 合理歸納，選好對(duì)象

例5在m×n的格子紙中填入mn個(gè)兩兩不同的數(shù)字，用紅筆圈出每行最大的s個(gè)數(shù)，用藍(lán)筆圈出每列最大的t個(gè)數(shù)，那么至少有st個(gè)數(shù)同時(shí)被紅藍(lán)筆圈出．

證明對(duì)s+t用數(shù)學(xué)歸納法．

(1)當(dāng)s+t=2時(shí)，s=t=1，結(jié)論成立，因?yàn)樽畲蟮囊粋€(gè)數(shù)一定同時(shí)被紅藍(lán)筆圈出.

(2)假設(shè)當(dāng)s+t=k時(shí)結(jié)論成立,則當(dāng)s+t=k+1時(shí)，分情況討論：

①若在某一行中有s個(gè)數(shù)同時(shí)被紅藍(lán)筆圈出，則將這行刪去，在剩下的表中用黃筆圈出每列中最大的t-1個(gè)數(shù)(注意：被黃筆圈出的數(shù)必已用藍(lán)筆圈出).由歸納假設(shè)可知，至少有s(t-1)個(gè)數(shù)同時(shí)被紅黃筆圈出．再加上被刪去的一行的s個(gè)同時(shí)被紅藍(lán)筆圈出的數(shù)，格子紙中同時(shí)被紅藍(lán)筆圈出的數(shù)至少有st個(gè)．

②若在某一列中有t個(gè)數(shù)同時(shí)被紅藍(lán)筆圈出，則同理可證．

下面證明，情況①和情況②必有一種成立．

把格子紙中所有填數(shù)減序排列記為b1,b2,…,bmn，顯然b1同時(shí)被紅藍(lán)筆圈出，記第1個(gè)不被紅筆和藍(lán)筆圈出的數(shù)為br．若br不被紅筆圈出，則與br同行的數(shù)至少有s個(gè)比br大，于是由br的定義可知,這s個(gè)數(shù)全被紅藍(lán)筆圈出;若br不被藍(lán)筆圈出，則與br同列的數(shù)至少有t個(gè)比br大，于是這t個(gè)數(shù)全被紅藍(lán)筆圈出．

根據(jù)(1)和(2)，可知結(jié)論成立．

評(píng)注對(duì)于與正整數(shù)s，t有關(guān)的命題，常用的思考方法是對(duì)s，t或者s+t進(jìn)行歸納．

6 曲中求伸，強(qiáng)化命題

有些命題P(n)直接用數(shù)學(xué)歸納法處理時(shí)，難以實(shí)現(xiàn)從n到n+1的過(guò)渡；然而比P(n)更強(qiáng)的命題Q(n)，用數(shù)學(xué)歸納法證明時(shí)反顯簡(jiǎn)單，因此需要對(duì)原命題給予加強(qiáng)．

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

證明用數(shù)學(xué)歸納法證明不等式:

(1)當(dāng)n=1時(shí)，

不等式成立．

(2)假設(shè)當(dāng)n=k時(shí)，不等式成立，即

則當(dāng)n=k+1時(shí)，

即當(dāng)n=k+1時(shí)不等式也成立．

根據(jù)(1)和(2)，可知不等式對(duì)任何n∈N*都成立．

7 欲擒故縱，推廣命題

對(duì)僅與某些較大的正整數(shù)有關(guān)的命題，可以考慮把它推廣到任意正整數(shù)n，再用數(shù)學(xué)歸納法證明推廣后的命題．這種“欲擒故縱”的解題策略也可以解決數(shù)學(xué)競(jìng)賽中的許多問(wèn)題．

證明用數(shù)學(xué)歸納法證明:對(duì)n≥1，有不等式

(1)當(dāng)n=1時(shí)，x2≥3x1>x1=a．

(2)假設(shè)不等式對(duì)不大于k的數(shù)都成立，則

更進(jìn)一步，由x1>0，得x2,x3,…,xk>0，于是

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

根據(jù)(1)和(2)，可知

于是，對(duì)足夠大的n，有xn+1>a·n!>2 010!．

8 孿生命題，螺旋歸納

在命題論證中，有時(shí)會(huì)出現(xiàn)一個(gè)命題的2個(gè)部分“蹺蹺板式連環(huán)相套”的現(xiàn)象．對(duì)付這種現(xiàn)象的一種辦法就是：將原來(lái)對(duì)一個(gè)命題的證明，變?yōu)檐E蹺板歸納式的同時(shí)證明一對(duì)孿生命題．這種歸納證明的方法也稱為螺旋歸納法．

例8證明:在斐波那契數(shù)列中，有

(1)當(dāng)n=1時(shí)，在P(n)中，

在Q(n)中，

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

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

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

也就是說(shuō)當(dāng)n=k+1時(shí),等式P(n)和Q(n)都成立．

根據(jù)(1)和(2)，可知等式P(n)和Q(n)對(duì)任何n∈N*都成立．

9 弱化命題，以退求進(jìn)

數(shù)學(xué)歸納法的另外一種命題轉(zhuǎn)化形式是:先證一個(gè)比原命題弱的命題；然后以此為基礎(chǔ)，再去證明原命題．弱化命題能起到減弱證明難度、分散證明難點(diǎn)，實(shí)現(xiàn)以退求進(jìn)的作用．

例9函數(shù)f(x)是定義在正整數(shù)上且取值為正整數(shù)的函數(shù)，有f(n+1)>f(f(n))，證明：對(duì)一切正整數(shù)n，都有f(n)=n．

證明先用數(shù)學(xué)歸納法證明一個(gè)較弱的命題：已知m,n∈N*，若m≥n，則

(1)當(dāng)n=1時(shí)，對(duì)一切正整數(shù)m≥1，都有f(m)≥1，因此式(1)成立．

(2)假設(shè)當(dāng)n=k時(shí)，式(1)成立.即若m≥k，則f(m)≥k，m,k∈N*．從而當(dāng)m≥k+1時(shí)，由m-1≥k，得

f(m-1)≥k.

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

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

于是

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

又因?yàn)閒(m)∈N*，所以f(m)≥k+1，也就是說(shuō)當(dāng)n=k+1時(shí),式(1)也成立．

根據(jù)(1)和(2)，可知式(1)對(duì)任何m≥n(m,n∈N*)都成立．

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

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

于是函數(shù)f(x)在正整數(shù)集上單調(diào)遞增，從而

n≤f(n)

又因?yàn)閒(n)∈N*，所以f(n)=n．

評(píng)注本題中的條件以不等式的形式給出，而結(jié)論以等式的面目給出，難以一步證明成功，因此考慮弱化命題．

[1] 蘇淳.漫話數(shù)學(xué)歸納法的應(yīng)用技巧[M].合肥:中國(guó)科學(xué)技術(shù)大學(xué)出版社，1992.