摘要：本文主要介绍数学归纳法在不同类型证明题中的应用。如初等数学，数学归纳法常常用来证明一类与自然数有关的命题或用于数列中；在高等数学中，数学归纳法应用于高等代数，图论等各种分支中。通过本文的介绍，希望帮助读者总结数学归纳法的证明技巧 。
关键词： 拉姆塞定理；归纳法公理；演绎法
中图分类号：G633.6 文献标识码：B 文章编号：1672-1578（2012）02-0160-02
数学归纳法是一种十分重要的数学方法，应用此法可以解决很多难题，下题是图论中著名的拉姆塞定理的特殊情形。
给出平面上n个点，每两点连接一条边，得到C?2?n 条边；这n个点和C?2?n条边构成n阶完全图k?n，把k?n的边染色使得每条边都要染色，而且只能染红色或蓝色，对于如何异于1的自然数p,q,无论kn的边怎样染色，n至少应该多大，才能使染色的结果必有一个全部边都是红色的K?p或者有一个全部边都是蓝色K?q？如果这个最小数存在，就记为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)2?n?2n+1 (1)
(B)2?n?n?2 (2)
解：（A）若n=1，∵27，∴（1）成立。（初值为3，不是1）
假设有某个整数n≥3，使（1）成立。（归纳法假设，往证2?n?+?1>2(n+1)+1）
∵2?n?+?1=2×2?n=2?n+2?n>2?n=2?n+2n+1=2?n-2+2(n+1)+1，
当n≥3时，2n-2>0，∴2?n?+?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）成立，（归纳法假设，往证2?n?+?1>（n+1）?2）
∵2?n?+?1=2×2?n=2?n+2?n>n?2+2?n>n?2+2n+1 （依（1））
故2?n?+?1>(n+1)?2，即n+1时，（2）亦成立，依数学归纳法，n≥5时 ,(2)成立，故知使（2）成立的n值为1和大于或等于5的一切整数值。
数学归纳法的第二步假设有某个命题成立，论证n+1亦使命题成立，这是基本形式。可以把假设改为：有某个n∈ N，使对于一切小于或等于n的自然数，命题成立，如下例：
例2：设S=x+1x ，求证x?n+1x?n 必可表为S的多项式（n为任何自然数）
证明：若n=1，1x=s，命题成立。
假设有某个n∈ N，使对于≤n的一切自然数，命题成立，（这是归纳假设，即假设1x ，x?2+1x?2 ,…，x?n+1x?n 等式都可以表示为S的多项式，论证x?n?+?1+1x?n?+?1 也可以表示为S的多项式）因为，x?n?+?1+1x?n?+?1 =（x?n+1x?n）（x+1x ）－（x?n?-?1+1x?n?-?1 ）,依归纳法假设，x?n+1x?n ,x+1x ,x?n?-?1+1x?n?-?1 都可以表示为S的多项式，故 x?n?+?1+1x?n?+?1也可以表示为S的多项式。依数学归纳法，证得不论n为任何自然数，x?n+1x?n 必可表为S的多项式。上面证法的推导过程可用图表示如下：
1→(1→ 2)→(1,2→3)→(1,2,3→4)→(1,2,3,4→5)→… … …
图上显示可以得到任何自然数。
从上例，可见题目求证的公式或有确定的表达形式，应用数学归纳法解决问题的困难不是很大。否则，既要找到表示形式，又要用数学归纳法证明结论，那就困难的多了，而且主要的困难在于前者，即探索结论的表示形式，如下例：
例3：设平面上有n条直线，每2条直线必相交，而且无3条直线共点（简称为在一般位置）分平面为a?2(n)个部分，求a?2(n)。
探索：若平面上没有直线，只有整个平面a?2(0)=1，若平面上有一条直线，分平面为两部分，a?2(1)=2，若平面上有两条直线相交，分平面为4个部分，a?2(2)=4，若平面上3直线在一般位置，分平面为7部分，a?2(3)=7，考虑到7=C?0?3 +C?1?3 +C?2?3 （C?r?n 表n物取r的组合数，且有补充定义 C?0?3=1，C?0?0 =1，以及 C?r?n=0，若r>n），而且1,2,4分别表示为：
a?2(0)=1=C?0?0 +C?1?0 +C?2?0
a?2(1)=2=C?0?1 +C?1?1 +C?2?1
a?2(2)=4=C?0?2 +C?1?2 +C?2?2
因而可以猜想，
a?2(n)=C?0?n +C?1?n +C?2?n （1）
以下用数学归纳法证明（1）
证：若n=0，（1）成立。
假设有某个非负数n使（1）成立（这是归纳法假设）往证：
a?2(n+1)=C?0?n?+?1 +C?1?n?+?1 +C?2?n?+?1 （2）
平面上在一般位置的n条直线分平面为a?2(n)个部分，添加第n+1条直线，构成在一般位置的n+1条直线。这条第n+1条直线与原n条直线有n个交点；这第n+1条直线被分为n+1段，每一段把原来n条直线所分出的一部分分为2部分，既增加一个部分，故第n+1条直线使原来a?2(n)个部分添加n+1个部分，因此：
a?2(n+1)=a?2(n)+n+1
因为n+1=1+n=C?0?n? +C?1?n
且依（1）
a?2(n+1)= C?0?n? +C?1?n + C?2?n+C?0?n? +C?1?n
=C?0?n+(C?1?n +C?0?n)+(C?2?n +C?1?n )
=C?0?n?+?1 +C?1?n?+?1+C?2?n?+?1
这就是(2)，故依数学归纳法，不论n为任何非负整数，（1）恒成立。
以上两个例子使用第一归纳法证明的；还有一种证明方法叫第二数学归纳法：如果关于自然数n的某个命题P(n)具备如下条件：
(1)P(1)真；
(2)k∈ N,n 以上介绍的是数学归纳法在初等数学中的应用，其实数学归纳法作为一种严格的推理方法，也广泛应用于高等数学的证题中。
如引入中有关图论问题的拉姆赛定理的证明。
证明：因为红蓝两色可以对换，故若R(p,q)存在，则必有R（p,q）=R(q,p) （1）
若p=2，k?2就是一条边，这就是红k?2，否则，如果没有红边，既全部边都是蓝色的，k?q就蓝k?q，
故R(2,q)=q （2）
图（1）
依(1)可知
R(p,2)=p （3）
考虑p=3，q=3的情况，可以证明k3的边染色，不能保证必有一个红k3（三角形），或者必有一个蓝k?3，如图（1）（红边为实边，蓝边为虚边）所示，染色的结果既没有一个红三角形，也没有一个蓝三角形。但可以证明k?6的染色，一定会有一个红三角形，或者有一个蓝三角形，如图（2），设P为顶点，P与另外5个顶点连接为5边，染色之后，（A）可能至少有3条红边，即至多有2条蓝边，（B）也可能至少有3条蓝边，即至多有2条红边，对于（A），设PA，PB，PC三边都是红边，若△ABC有红边，设为AB，则△PAB为红三角形；若△ABC无红边，它就是蓝三角形，对于（B）只需把（A）的证明中红蓝两色对换，便得出了必有红三角形或必有蓝三角形的结论。总之不论k?6的边怎么染色，必有一个红三角形或必有蓝三角形，故R(3,3)=6。
这是数学归纳法用于图论中的例子。
图（2）
下面再看数学归纳法用于高代的例子。
例4：设V?1，V?2，V?3，…，V?s是线性空间V的s个非平凡的子空间，证明：V中至少有一个向量不属于V?1，V?2，…，V?s中的任何一个。
证明：对s用数学归纳法。
当s=2时，因为V?1是非平凡子空间，故存在α V?1，如果α V?2，结论成立；如果α ∈V?2，则由V?2也是非平凡子空间，故存在β V2，若β V?1，则结论已成立；若β V?1，则
α V?1，β∈ V?2，α∈ V?2，β V?2 ①
于是用反证法可证α+β V?1，α+β V?2，事实上，若α+β∈ V?1，又β∈ V?1，这与①矛盾，
故α+β V?1，同理证明α+β V?2。
故当s=2时，结论成立。
假定对s-1个非平凡的子空间结论成立，即在v中存在向量α，使α V?i，i=1，2，…，s-1，对第s个子空间V?s，若α V?s，结论成立；若α ∈V?s，则由于V?s为非平凡子空间，故存在β V?s，于是对任意数k，向量k*α+β V?s（如果kα+β∈ V?s，β=（kα+β）-kα∈ V?s与β V1中?s矛盾），且对于不同的数k?1，k?2，向量k?1α+β，k?2α+β不属于同一个V?i（1≤i≤s-1）（如果k?1α+β，k?2α+β属于同一个V?i，则（k?1α+β）-（k?2α+β）=（k?1-k?2）α∈ V?i，得α∈ V?i与α V?i矛盾）。
令取s个互不相同的数k?1，k?2，…，k?s，则s个向量
k?1α+β，k?2α+β，…k?i?-?1α+β，k?sα+9β
至少有一个不属于V?1，V?2，…，V?s?-?1，这样的向量即满足要求。
综上所述，数学归纳法是十分重要的数学证明方法，仔细体会本文中例题，熟悉数学归纳法的用法和证明技巧。要抓住数学归纳法中关键步骤：（1）验证n=1时结论正确；（2）假设当n=k时结论正确，证明当n=k+1时结论也正确，两个步骤缺一不可。
参考文献：?
[1] 《中学数学研究》华南师大数学系《中学数学研究》编辑部 2001.1.10出版 总第229期?
[2] 《奥数教程》华东师范大学出版社 200.10第一版?
[3] 《数学奥林匹克解题研究》 北京师范大学出版社 1988.7第一版