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

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

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

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

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

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

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

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

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

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

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

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

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

1 巧妙添項，配湊形式

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

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

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

能被133整除，命題成立．

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

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

評注在本題中，將11k+2+122k+3變形為

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

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

2 大膽嘗試，先猜后證

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

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

3 增多起點，加大跨度

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

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

證明(1)當(dāng)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|)≥

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

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

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

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

證明考慮數(shù)列

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

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

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

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

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

特別地，對h=1，有bn<1+1=2．

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

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

5 合理歸納，選好對象

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

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

(1)當(dāng)s+t=2時，s=t=1，結(jié)論成立，因為最大的一個數(shù)一定同時被紅藍(lán)筆圈出.

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

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

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

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

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

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

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

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

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

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

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

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

不等式成立．

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

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

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

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

7 欲擒故縱，推廣命題

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

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

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

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

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

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

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

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

8 孿生命題，螺旋歸納

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

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

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

在Q(n)中，

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

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

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

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

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

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

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

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

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

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

(2)假設(shè)當(dāng)n=k時，式(1)成立.即若m≥k，則f(m)≥k，m,k∈N*．從而當(dāng)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，也就是說當(dāng)n=k+1時,式(1)也成立．

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

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

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

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

n≤f(n)

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

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

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