螺旋式數學歸納法的應用

鄭宏寶

我們通常所說的數學歸納法分為兩種，第一數學歸納法和第二數學歸納法。第一數學歸納法，即假設對n=k時成立，通過證明對n=k+1時也成立完成證明。第二數學歸納法實際上跟第一數學歸納法沒有本質區別，不過是把假設條件變成對n≤k均成立。這兩種數學歸納法的考題一般是比較簡單的，即只需要猜出結論，直接代入驗證即可。所以一般情況下，我們的重心在于猜，而不在于后面的證明。但在競賽中對于數學歸納法的應用不僅限于此，即使猜出來了結論，歸納證明也是十分復雜的。這里介紹一種新的數學歸納法，在歸納證明遇到困難的時候可以嘗試采用這種方法。我們先看一個比較簡單的例子：

例1 數列{an}定義為a1=a2=1，an+2=an+1+an，求證：當n≥2時，a2n-1必是數列中某兩項的平方和，a2n必是數列中某兩項的平方差。

分析 這個數列是我們非常熟悉的Fibonacci數列，不妨先把前幾項寫出來a1=1，a2=1，a3=2，a4=3，a5=5，a6=8，a7=13，a8=21，有a3=a21+a22，a5=a22+a23，a7=a23+a24，…，a4=a23-a21，a6=a24-a22，a8=a25-a23，…，于是猜想a2n-1=a2n-1+a2n，a2n=a2n+1-a2n-1（n≥2），然后用數學歸納法完成證明。

證明 數列的前4項為a1=1，a2=1，a3=2，a4=3，有a3=a21+a22，a4=a23-a21。

假設a2n-1=a2n-1+a2n，a2n=a2n+1-a2n-1（n≥2），則a2n+1=a2n+a2n-1=a2n+a2n+1，

a2n+2=a2n+1+a2n=a2n+1+a2n+a2n+1-a2n-1

=a2n+1+a2n+（a2n+1-a2n-1）=a2n+1+a2n+an（2an+1-an）=a2n+1+2anan+1=a2n+1+2anan+1+a2n-a2n=（an+1+an）2-a2n=a2n+2-a2n。

故對一切自然數n≥2，有a2n-1=a2n-1+a2n，a2n=a2n+1-a2n-1。即當n≥2時，a2n-1必是數列中某兩項的平方和，a2n必是數列中某兩項的平方差。

這道題解法很自然，實際上用到了螺旋式數學歸納法的思想，即我們要證明的并不是一個結論，可以寫為：An：a2n-1=a2n-1+a2n，Bn：a2n=a2n+1-a2n-1。如果兩個結論不放在一起，而是分開去單獨證明，是十分困難的，我們用的方法是先假設An和Bn同時成立，然后證明An+1成立，再根據An+1和Bn證明了Bn+1成立，于是完成了證明，此方法即是螺旋式數學歸納法。

這道題直接告訴了有兩個結論需要去證明，所以思路比較直接，但是如果題目中只單單告訴了一個結論，另一個結論需要自己去尋找，就比較困難了。

例2 數列{an}滿足a0=a1=a2=1，an+2=-an-1+9anan+1-a2n-a2n+1-1an+an+1，n≥1。求證：對任意的正整數n，an是整數。

分析 這個數列形式已經十分復雜，求其通項顯然是行不通的，但是注意到題目中要證明的只是an是整數，所以自然想到，如果能證明an+1=pan+qan-1，或者滿足類似的形式即可。但是這個遞推式也是無法得到的，于是想到了數學歸納法，類似上題先寫幾項猜猜看，a0=a1=a2=1，a3=2，a4=3，a5=7，a6=11，a7=26，a8=41，似乎找不到我們想要的遞推式，但是如果把奇數項和偶數項分開看，容易發現a2n+1=3a2n-a2n-1，a2n+2=2a2n+1-a2n，如果能證明這兩個式子，即完成了證明。

證明 數列的前幾項為a0=a1=a2=1，a3=2，a4=3，有a3=3a2-a1，a4=2a3-a2。

假設a2n+1=3a2n-a2n-1，a2n+2=2a2n+1-a2n（n≥1），我們先證奇數項，則

a2n+3=-a2n+9a2n+1a2n+2-a22n+1-a22n+2-1a2n+1+a2n+2。

用分析法，即證-a2n+9a2n+1a2n+2-a22n+1-a22n+2-1a2n+1+a2n+2=3a2n+2-a2n+1

9a2n+2a2n+1-a22n+1-a22n+2-1=（3a2n+2-a2n+1+a2n）（a2n+1+a2n+2）

7a2n+2a2n+1-4a22n+2-1=a2na2n+1+a2na2n+2a2n+2（7a2n+1-4a2n+2-a2n）=a2na2n+1+1a2n+2（3a2n-a2n+1）=a2na2n+1+1a2n+2a2n-1=a2n+1a2n+1。

證到這里我們發現，直接歸納去證明顯然是證不出來的，因為此數列是遞推的，后面的性質不單單是由遞推式決

定，還由前幾項決定，可是我們在用數學歸納法的時候不可能一直算到數列的前幾項。至此，雖然沒有證明出來我們想要的結論，但是我們很神奇的發現了一個新的結論，即是a2n+2a2n-1=a2n+1a2n+1，這個結論是由分析法得到的，也就是說如果結論正確，這條性質肯定是對的。將這條性質帶回去檢驗一下，我們發現對于前幾項確實是滿足的。事實上，是有an+2an-1=an+1an+1的。

下面我們用螺旋式數學歸納法證明，其中An：a2n+1=3a2n-a2n-1，a2n+2=2a2n+1-a2n，Bn：an+2an-1=an+1an+1。根據上述的分析法，我們知道由An和B2n可以推出a2n+3=3a2n+2-a2n+1，

下面我們根據An和B2n和a2n+3=3a2n+2-a2n+1，來推出B2n+1成立

即證a2n+3a2n=a2n+2a2n+1+1成立，（3a2n+2-a2n+1）a2n=a2n+2a2n+1+1

3a2n+2a2n-a2n+2a2n+1=a2n+1a2n+1a2n+2（3a2n-a2n+1）=a2n+1a2n+1a2n+2a2n-1=a2n+1a2n+1

由假設B2n成立，即知上式成立。

對于偶數項同理可證，所以有a2n+1=3a2n-a2n-1，a2n+2=2a2n+1-a2n，因為前三項都是整數，顯然an都是整數，至此完成了證明。

此題的關鍵在于需要自己找到該數列另一個非常好的性質，即an+2an-1=an+1an+1，而往往這種性質并不是那么容易發現，是在我們用分析法證明的過程中發現的，進而用螺旋式數學歸納法完成證明。那自然就會想，對于Bn的假設是我們自己給出來的，我們可以在對An證明的過程中任意一步走不下去的時候就設它為Bn，假設它成立，然后歸納出An+1，這種做法理論上是可行的，但是接下來需要做的并不是去證An+1，而是需要去證明Bn+1成立，往往接下來證明的困難程度取決于Bn的形式，也就是說，Bn的形式越簡單，越容易完成接下來的證明，所以我們在自己去構造Bn時，一定要盡可能的讓Bn的形式簡潔明了，容易驗證，就像例子中的an+2an-1=an+1an+1一樣。