1数学归纳法
1 基本原理
数学归纳法是以皮亚诺的归纳原理为数学基础.由于可以证明归纳公理和最小数原理等价,所以人们常用最小数原理证明数学归纳法.我们先对最小数原理作一介绍.
最小数原理 设M是自然数集的一个非空子集,则M中必有最小数,即?n0?M,使得?n?M,均有n?n0.
为了便于说明数学归纳法的其他表现形式,我们先证明如下结论: 定理1 设A是一个非空集合, A1,A2,???,AK,???均为非空集合,
A?A1?A2?????AK????,若?n?A1,有命题P(n)成立.又在假设?n?Ak,命题
P(n)成立的前提,能推出?n?Ak?1,命题P(n)成立,则?n?A,命题P(n)成立.
证 用反证法.若结论不成立,即?n0?A,使得命题P(n)不成立,因为
A?A1?A2?????AK????,所以n属于某个Ai,令B?{i?n?Ai,使得P(n)不成立},
则B??,且B?N.由最小数原理知, B中有最小数s,由于s是集合B的最小数,又
?n?A1,P(n)成立,所以s?1,所以s?1?1.由s的规定知, ?n?As?1,命题P(n)成立,
再由定理的条件知?n?As,命题P(n)均成立,这与?n?As,使得P(n)不成立相矛盾,故原假设不成立,即定理结论成立.
定理2 (跳跃归纳法) 设P(n)是关于正整数n的命题,若P(1),P(2),???,P(l),(l?2)均成立,又在假设P(k)成立的前提下,能推出P(k?l)成立,则对于一切正整数n,P(n)均成立.
在跳跃归纳法中,人们常把整数l称为归纳跨度.
在定理1中,对集合Ak作出不同的规定,我们还可以得到如下形式的倒退归纳法. 定理3 (倒退归纳法) 设对于n?n0(n0?1),命题P(n0)成立,若由P(k)成立能推出
P(k?1)成立, (k?n0),则对于n?{1,2,???,n0},命题P(n)均成立.
定理4 (倒退归纳法) 若对于n?2,k?1,2,???,命题P(n)成立.又由P(k)成立能推出P(k?1)成立,则对于n?N,命题P(n)均成立.
除上述表现形式外,我们还可以根据需要写出不同形式的数学归纳法.
1
k
3 方法解读
用数学归纳法证明命题，要注意如下几点：
（1）注意归纳起点的选择.有些关于正整数n的命题，由P(1)成立不一定能推出P(2)成立，由P(2)成立也不一定能推出P(3)成立，只有从某个n0开始，当k?n0时，由P(k)成立能推出P(k?1)成立，此时归纳起点可从n0开始，对于P(1),P(2),???,P(n0?1)的证明则另想他法.
（2）注意归纳形式的选择.归纳法有多种表现形式，应把握题型特点，选择适当的归纳法.例如，若由命题P(k)成立不易推出P(k?1)成立，而由命题P(k)成立易推出
P(k?l) (l?2)成立，这时应用跳跃归纳法.又如，若由P(k)成立不易推出P(k?1)成立，
而由P(k)成立易推出P(k?1)成立，这时应选择倒退归纳法.
(3)注意加强命题.有些关于自然数的命题P(n)，直接用归纳法证明P(n)成立比较困难，这时可考虑证明P(n)的加强命题f(n)，这里f(n)是P(n)的充分条件.
(4)注意命题的活化.有些关于某些特定整数的命题P(n0)，直接证明比较困难时，这时可考虑证明命题P(n)，而将P(n0)看成是P(n)的特例.
(5)注意创造条件用归纳假设.有些关于正整数的命题P(n)，在证明P(k?1)时不能直接运用归纳假设，这时应将P(k?1)的条件作适当的转化，使之满足归纳假设的条件，进而用归纳假设完成证明.
（6）注意归纳变量的选择.有些关于双变元的命题P(m,n)，可用双变元归纳法证明.若用单变元归纳法证明，这时应注意选择归纳变量是m还是n.
例1 试证明对任何自然数n?6，每一个正方形都可分成n个正方形.
证 当 n?6,7,8 时，由图1知结论成立.
图1
假设对于n?k(k?6)时结论成立，那么对于n?k?3，我们先将正方形分成k个正方形，
2
再将这k个正方形中的一个分成4个小正方形，从而得到k?3个正方形，即n?k?3时结论成立.由归纳法原理知结论成立.
例2 设f(n)是N??N?的映射，满足： （1）f(2)?2；
（2）?m,n?N?，有f(mn)?f(m)f(n)； （3）当m,n?N?且m?n时有f(m)?f(n). 证明对于任意正整数n，都有f(n)?n.
证 由条件（1）及（2），不难用数学归纳法证明：?k?N?，有f(2)?2.
对于n?N?，当n?1时，因为f(1)?N?，所以f(1)?1.又由（3）知 f(1)?f(2)?2，所以f(1)?1，从而有f(1)?1.
k又当n?1且n??2(k?N?)时，必存在这样的m?N?，使得
kk2m?n?2m?1，
设n?2m?s,1?s?2m?1,由于
2m?f(2m)?f(2m?1)?f(2m?2)?????f(2m?2m?1)?f(2m?1)?2m?1，
又 f(2m?j)?N?，从而有
f(2m?j)?2m?j,1?j?2m?1.
所以 f(2?s)?2?s, 所以 f(n)?n.
例3 证明：存在正整数的无穷数列{an}，满足
mma1?a2?a3????,
使得对所有正整数n，a1?a2?????an都是完全平方数.
证 我们证明如下命题：存在正整数的无穷数列{an}，a1?a2?a3????,使得对任意正整数n，a1?a2?????an为奇数的平方.下面我们归纳构造满足条件的数列.
222222 3
对于n?1，取a1?5.
假设对于n?k,a1,a2,???,ak已给定，满足 a1?a2?????ak,且对于
2.那么对于n?k?1, 设 1?i?k,a12?a22?????ai均为奇数的平方
a12?a22?????ak2?(2m?1)2，
取ak?1?(2m2?2m)2,则有
a12?a22?????ak2?ak?12?(2m?1)2?(2m2?2m)2?(2m?2m)?2(2m?2m)?1?(2m2?2m?1)2,所以a12?a22?????ak2?ak?12也是奇数的平方.由归纳法原理知满足条件的数列存在.
例4 设 an?1?222
11?????，求证：当n?2时，有 2nan2?2(aa2a3??????n). 23n分析 由ak?2(2aaaa2a3a??????k)，推不出 ak?12?2(2?3?????k?1).事实23k23k?1上，因为ak?1?(ak?21221)?ak2?ak?,若用归纳假设放缩不等式，则有 2k?1k?1(k?1)ak?12?2(a22a?2(22?2(aa2a321??????k)?ak?23kk?1(k?1)2aa221?3?????k?1)?ak?ak?1?3k?1k?1k?1(k?1)2 aa21?3?????k?1)?(ak?ak?1)?3k?1k?1(k?1)2aa2a3211??????k?1)?(?)?23k?1k?1k?1(k?1)2
ak?1a2a31?2(??????)?(1)223k?1(k?1)?2(（1）式右边比我们要证明的结论小，这说明用归纳假设放缩时已放缩过度.为此我们希望通过加强命题的方法来证明.设g(n)是一个非负数列，我们希望能有
4
an?2(2aa2a3??????n)?g(n)， （2） 23n下面我们分析g(n)应满足的条件.若结论成立，因为
ak?12?(ak?1221)?ak2?ak?, 2k?1k?1(k?1)用归纳假设 ak?2(2aa2a3??????k)?g(k)，则有 23kak?12?2(aa2a321??????k)?g(k)?ak?23kk?1(k?1)2aa?a1??2(2?3?????k?1)?g(k?1)??g(k)?g(k?1)??23k?1(k?1)2??要 ak?1?2(2
aa2a3??????k?1)?g(k?1)，只要 23k?1g(k)?g(k?1)?1?0 2(k?1)即 g(k?1)?g(k)?1. （3）
(k?1)2也就是说，若我们想通过数学归纳法证明（2）式，只需证（2）式中的g(n)满足（3）式即可.现在我们取g(n)?命题:
2 对于n?2，有an?2(1，容易验证g(n)满足（3）式，从而我们能用数学归纳法证明加强naa2a31??????n)? . （4） 23nn(4)式的证明留给读者去完成.
例5 设S为一个2010元集合，N为满足0?N?2进行黑白染色，使得
（1）任意两个白子集的并集仍是白子集； （2）任意两个黑子集的并集仍是黑子集； （3）恰有N个白子集.
证 当n?1时，S的子集为S,?.对于0?N?2，将它们中的N个子集染成白色，其余子集染成黑色，这种染色的结果满足3个条件.
假设对于n?k，结论成立，那么对于n?k?1,S?{a1,a2,???,ak,ak?1},将S的不含
5
2010的整数，证明可以将S的子集