数学归纳法的巧妙应用及证明技巧

摘要：本文主要介绍数学归纳法在不同类型证明题中的应用。如初等数学，数学归纳法常常用来证明一类与自然数有关的命题或用于数列中；在高等数学中，数学归纳法应用于高等代数，图论等各种分支中。通过本文的介绍，希望帮助读者总结数学归纳法的证明技巧 。

关键词： 拉姆塞定理；归纳法公理；演绎法

中图分类号：G633.6 文献标识码：B 文章编号：1672-1578（2012）02-0160-02

数学归纳法是一种十分重要的数学方法，应用此法可以解决很多难题，下题是图论中著名的拉姆塞定理的特殊情形。

给出平面上n个点，每两点连接一条边，得到C2n 条边；这n个点和C2n条边构成n阶完全图kn，把kn的边染色使得每条边都要染色，而且只能染红色或蓝色，对于如何异于1的自然数p,q,无论kn的边怎样染色，n至少应该多大，才能使染色的结果必有一个全部边都是红色的Kp或者有一个全部边都是蓝色Kq？如果这个最小数存在，就记为R(p,q). R(p,q)叫拉姆塞数。

这个著名定理的证明用的就是数学归纳法。

数学归纳法是一种十分重要的数学方法，它的根据使归纳法公理，若数集N包含1，而且若自然数k∈ N,则必定有k+1∈ N,那么N就是自然数集。数学归纳法的实质是演绎法，而不是归纳法。

应用数学归纳法证明某一命题P，第一步，检验初值，n=1时，P成立。第二步，提出归纳法假设，设对于某个n值，P成立，证明n+1时P亦成立，通过两次证明，就证明了不论n为任何自然数，P成立。

例1：对怎样的自然数n，以下不等式成立:

(A)2n2n+1 (1)

(B)2nn2 (2)

解：（A）若n=1，2

若n=2，4

若n=3，8>7，（1）成立。（初值为3，不是1）

假设有某个整数n≥3，使（1）成立。（归纳法假设，往证2n+1>2(n+1)+1）

2n+1=2×2n=2n+2n>2n=2n+2n+1=2n-2+2(n+1)+1，

当n≥3时，2n-2>0，2n+1>2(n+1)+1

即n+1时，（1）亦成立 （第二步证明）

依数学归纳法，当n≥3时，（1）式成立

（B）令n=1，代入（2）知（2）成立。

分别令n=2,3,4，代入（2）知（2）不成立。

令n=5，代入（2）知（2）成立。（5为初值）

假设有某个整数n≥5，使（2）成立，（归纳法假设，往证2n+1>（n+1）2）

2n+1=2×2n=2n+2n>n2+2n>n2+2n+1 （依（1））

故2n+1>(n+1)2，即n+1时，（2）亦成立，依数学归纳法，n≥5时 ,(2)成立，故知使（2）成立的n值为1和大于或等于5的一切整数值。

数学归纳法的第二步假设有某个命题成立，论证n+1亦使命题成立，这是基本形式。可以把假设改为：有某个n∈ N，使对于一切小于或等于n的自然数，命题成立，如下例：

例2：设S=x+1x ，求证xn+1xn 必可表为S的多项式（n为任何自然数）

证明：若n=1，1x=s，命题成立。

假设有某个n∈ N，使对于≤n的一切自然数，命题成立，（这是归纳假设，即假设1x ，x2+1x2 ,…，xn+1xn 等式都可以表示为S的多项式，论证xn+1+1xn+1 也可以表示为S的多项式）因为，xn+1+1xn+1 =（xn+1xn）（x+1x ）－（xn-1+1xn-1 ）,依归纳法假设，xn+1xn ,x+1x ,xn-1+1xn-1 都可以表示为S的多项式，故 xn+1+1xn+1也可以表示为S的多项式。依数学归纳法，证得不论n为任何自然数，xn+1xn 必可表为S的多项式。上面证法的推导过程可用图表示如下：

1(1 2)(1,23)(1,2,34)(1,2,3,45)… … …

图上显示可以得到任何自然数。

从上例，可见题目求证的公式或有确定的表达形式，应用数学归纳法解决问题的困难不是很大。否则，既要找到表示形式，又要用数学归纳法证明结论，那就困难的多了，而且主要的困难在于前者，即探索结论的表示形式，如下例：

例3：设平面上有n条直线，每2条直线必相交，而且无3条直线共点（简称为在一般位置）分平面为a2(n)个部分，求a2(n)。

探索：若平面上没有直线，只有整个平面a2(0)=1，若平面上有一条直线，分平面为两部分，a2(1)=2，若平面上有两条直线相交，分平面为4个部分，a2(2)=4，若平面上3直线在一般位置，分平面为7部分，a2(3)=7，考虑到7=C03 +C13 +C23 （Crn 表n物取r的组合数，且有补充定义 C03=1，C00 =1，以及 Crn=0，若r>n），而且1,2,4分别表示为：

a2(0)=1=C00 +C10 +C20

a2(1)=2=C01 +C11 +C21

a2(2)=4=C02 +C12 +C22

因而可以猜想，

a2(n)=C0n +C1n +C2n （1）

以下用数学归纳法证明（1）

证：若n=0，（1）成立。

假设有某个非负数n使（1）成立（这是归纳法假设）往证：

a2(n+1)=C0n+1 +C1n+1 +C2n+1 （2）

平面上在一般位置的n条直线分平面为a2(n)个部分，添加第n+1条直线，构成在一般位置的n+1条直线。这条第n+1条直线与原n条直线有n个交点；这第n+1条直线被分为n+1段，每一段把原来n条直线所分出的一部分分为2部分，既增加一个部分，故第n+1条直线使原来a2(n)个部分添加n+1个部分，因此：

a2(n+1)=a2(n)+n+1

因为n+1=1+n=C0n +C1n

且依（1）

a2(n+1)= C0n +C1n + C2n+C0n +C1n

=C0n+(C1n +C0n)+(C2n +C1n )

=C0n+1 +C1n+1+C2n+1

这就是(2)，故依数学归纳法，不论n为任何非负整数，（1）恒成立。

以上两个例子使用第一归纳法证明的；还有一种证明方法叫第二数学归纳法：如果关于自然数n的某个命题P(n)具备如下条件：

(1)P(1)真；

(2)k∈ N,n

在数学归纳法证明中，试验P(1)成立是归纳法的基础，第二步P(k)P(k+1)是前一个命题真得出后继命题真的依据，这两步缺一不可，只有在这两步都完成后，才能根据第一、第二归纳法得出n ∈N，P(n)真的结论。

以上介绍的是数学归纳法在初等数学中的应用，其实数学归纳法作为一种严格的推理方法，也广泛应用于高等数学的证题中。

如引入中有关图论问题的拉姆赛定理的证明。

证明：因为红蓝两色可以对换，故若R(p,q)存在，则必有R（p,q）=R(q,p) （1）

若p=2，k2就是一条边，这就是红k2，否则，如果没有红边，既全部边都是蓝色的，kq就蓝kq，

故R(2,q)=q （2）

图（1）

依(1)可知

R(p,2)=p （3）

考虑p=3，q=3的情况，可以证明k3的边染色，不能保证必有一个红k3（三角形），或者必有一个蓝k3，如图（1）（红边为实边，蓝边为虚边）所示，染色的结果既没有一个红三角形，也没有一个蓝三角形。但可以证明k6的染色，一定会有一个红三角形，或者有一个蓝三角形，如图（2），设P为顶点，P与另外5个顶点连接为5边，染色之后，（A）可能至少有3条红边，即至多有2条蓝边，（B）也可能至少有3条蓝边，即至多有2条红边，对于（A），设PA，PB，PC三边都是红边，若ABC有红边，设为AB，则PAB为红三角形；若ABC无红边，它就是蓝三角形，对于（B）只需把（A）的证明中红蓝两色对换，便得出了必有红三角形或必有蓝三角形的结论。总之不论k6的边怎么染色，必有一个红三角形或必有蓝三角形，故R(3,3)=6。

这是数学归纳法用于图论中的例子。

图（2）

下面再看数学归纳法用于高代的例子。

例4：设V1，V2，V3，…，Vs是线性空间V的s个非平凡的子空间，证明：V中至少有一个向量不属于V1，V2，…，Vs中的任何一个。

证明：对s用数学归纳法。

当s=2时，因为V1是非平凡子空间，故存在α V1，如果α V2，结论成立；如果α ∈V2，则由V2也是非平凡子空间，故存在β V2，若β V1，则结论已成立；若β V1，则

α V1，β∈ V2，α∈ V2，β V2 ①

于是用反证法可证α+β V1，α+β V2，事实上，若α+β∈ V1，又β∈ V1，这与①矛盾，

故α+β V1，同理证明α+β V2。

故当s=2时，结论成立。

假定对s-1个非平凡的子空间结论成立，即在v中存在向量α，使α Vi，i=1，2，…，s-1，对第s个子空间Vs，若α Vs，结论成立；若α ∈Vs，则由于Vs为非平凡子空间，故存在β Vs，于是对任意数k，向量k*α+β Vs（如果kα+β∈ Vs，β=（kα+β）-kα∈ Vs与β V1中s矛盾），且对于不同的数k1，k2，向量k1α+β，k2α+β不属于同一个Vi（1≤i≤s-1）（如果k1α+β，k2α+β属于同一个Vi，则（k1α+β）-（k2α+β）=（k1-k2）α∈ Vi，得α∈ Vi与α Vi矛盾）。

令取s个互不相同的数k1，k2，…，ks，则s个向量

k1α+β，k2α+β，…ki-1α+β，ksα+9β

至少有一个不属于V1，V2，…，Vs-1，这样的向量即满足要求。

综上所述，数学归纳法是十分重要的数学证明方法，仔细体会本文中例题，熟悉数学归纳法的用法和证明技巧。要抓住数学归纳法中关键步骤：（1）验证n=1时结论正确；（2）假设当n=k时结论正确，证明当n=k+1时结论也正确，两个步骤缺一不可。

参考文献：

[1] 《中学数学研究》华南师大数学系《中学数学研究》编辑部 2001.1.10出版 总第229期

[2] 《奥数教程》华东师范大学出版社 200.10第一版

[3] 《数学奥林匹克解题研究》 北京师范大学出版社 1988.7第一版