数学归纳法的巧妙应用，本文主要内容关键词为：归纳法论文,巧妙论文,数学论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
本刊1998年第2 期登载了拙作《数学归纳法的根据和应注意要点》，对数学归纳法作初步的讨论。本文将作进一步的探讨，供读者参考。
数学归纳法的根据是归纳法公理，若数集N包含1， 而且若自然数k∈N，则必有k＋1∈N，那么，N就是自然数集。
数学归纳法的实质不是归纳法，而是演绎法。
应用数学归纳法证明某一命题P，第一步，检验初值，n＝1时，P成立。第二步提出归纳法假设，设对于某个n值，P成立，证明n＋1时， P亦成立。通过这两步，就证明了不论n为任何自然数，P成立。
上面指出的第一步要检验n＝1时，P成立。其实，这是使P成立的集N有最小值的意思，这个最小值可以是1，也可以是别的整数值。如下面例1。
例1 对怎样的自然数n，以下不等式成立：
（A）2[n]＞2n＋1。（1）
（B）2[n]＞n[2]。（2）
K[,q]的边染色。如果有一条红边，这就是红K[,2]。否则，如果没有红边，即全部边都是蓝色的，K[,q]就是蓝K[,q]，故
R（2，q）＝q。 （2）
依（1）可知
R（p，2）＝p。 （3）
考虑p＝3，q＝3的情形。可以证明k[,5]的边染色， 不能保证必有一个红k[ ,3]（三角形），或者必有一蓝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。 （4）
了解上面事实之后，可以应用数学归纳法证明下例：
例5 对于任意的自然数p≥2，q≥2，R（p，q）必存在。也即是说，存在最小自然数R（p，q）使对于自然数n≥R（p，q），K[,n]的任何边染色，必有一红K[,p]或者必有一蓝K[,q]。
证明：如上所论，已得到（1），（2），（3 ）诸式（这是数学归纳法的第一步）。
假设R（p，q－1），R（p－1，q）都存在。（归纳法假设， 往证R（p，q）存在。）令
n＝R（p，q－1）＋R（p－1，q），
考虑K[,n]的边染色，任取n点中的一点P，由此点作出的边有n －1条。任意作边染色后，此n－1条边中至少有R（p－1，q）条红边，或者至少有R（p，q－1）条蓝边。否则，至多有R（p－1，q）－1条红边，和至多R（p，q－1）－1条蓝边，合共至多有R（p－1，q）－1＋R（p，q－1）－1＝n－2条边，与有n－1条边矛盾。
若由P作出的红边有R（p－1，q）条，则这些边的非P的端点有R（p－1，q）个。这些端点构成R（p－1，q）阶完全图。这个图的任何边着色必有一红K[,p－1]，与P构成红K[,p]；或者必有一蓝K[,q]。
若由P作出的蓝边有R（p，q－1）条，只要把上文红蓝两色对换，便可证明有一个红K[,p]或有一个蓝K[,q]。故R（p，q）≤n，且R（p，q）必存在。
依数学归纳法，不论任何自然数p≥2，q≥2，R（p，q）恒存在。
上面证法中，第一步是R（p，2），R（2，p）存在，第二步是R （p，q－1），R（p－1，q）存在推出R（p，q）存在。这个推导的过程可以图解如下：
