螺旋式数学归纳法的应用

郑宏宝

我们通常所说的数学归纳法分为两种，第一数学归纳法和第二数学归纳法。第一数学归纳法，即假设对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一样。