竞赛中的数学归纳法

（一）数学归纳法的基本形式 （1）第一数学归纳法

设P(n)是一个与正整数有关的命题，如果: ①当nn0（n0N）时，P(n)成立；

②假设nk(kn0,kN)成立，由此推得nk1时，P(n)也成立，那么，根据①②对一切正整 数nn0时，P(n)成立．

*例1 （07江西理22）设正整数数列an满足：a24，且对于任何nN，有

11aan1112n2．

an111annn1（1）求a1，a3； （2）求数列an的通项an．

1111解：（1）据条件得2n(n1)2 ① 当n1时，

an1ananan1由2111221112822，即有22，解得a1．因为a1为正整数，故

4a14a137a2a1a1a21111a11．当n2时，由262，解得8a310，所以a39．

a344a32（2）由a11，a24，a39，猜想：ann．下面用数学归纳法证明: 2o1当n1，2时，由（1）知ann均成立；

22假设nk(k≥2)成立，akk，则nk1时由①得2o1111k(k1)22, 2ak1kakk1k2(k1)k(k2k1)(k1)2122ak1(k1)2ak1(k1)2,因为k≥2时， kk1k1k1k1(k1)21(k1)(k1)k(k1)(k2)≥0，所以20，1．k1≥1，所以0，1．

k1k1222*222又ak1N，所以(k1)≤ak1≤(k1),故ak1(k1)，即nk1时，ann成立．

2*oo由1，2知，对任意nN，ann．

此题在证明时应注意，归纳奠基需验证的初始值又两个，即n1和n2。

（2）第二数学归纳法

设P(n)是一个与正整数有关的命题，如果 ① 当nn0（n0N）时，P(n)成立；

② 假设nk(kn0,kN)成立，由此推得nk1时，P(n)也成立，那么，根据①②对一切正 整数nn0时，P(n)成立．

例2 已知对任意的nN,n1,an0且

aj1n3j(aj)2，求证：ann.

j1n32证：（1）当n1时，因为a1a1且a10，所以，a11，命题成立；

（2）假设nk时命题成立，即ajj(j1,2,L,k),当nk1时，因为

aa3jj1j1k1k3ja3k1(aj)a2j12k1，且

k3k1，

aj1k13j2(aj)(ajak1)(aj)2ak1ajak1

222j1j1j1j1k1kkk所以ak3k12ak1ajaj1kak10，于是a2k12ajak1，因为ajj(j1,2,L,k)，

j1k∴

ajj1k(k1)2,从而ak1ak1k(k1)0，解得ak1k1，akk（舍），即nk1时 2命题成立.

由（1）、（2）知，对一切自然数n(n1)都有ann成立.证毕.

这两种数学归纳法，是运用次数较多的方法，大家也比较熟悉，在这里就不赘述了。下面介绍一下数学归纳法的其它形式。

（二）数学归纳法的其他形式 （1）跳跃数学归纳法

① 当n1,2,3,,l时，P(1),P(2),P(3),,P(l)成立，

② 假设nk时P(k)成立，由此推得nkl时，P(n)也成立，那么，根据①②对一切正整数n1 时，P(n)成立．

例3 证明：任一正方形可以剖分成任意个数多于5个的正方形.

证：（1）对于n6,7,8可按如图进行分割, 假设当nk(k6)成立,当nk3时，只要将其中一个正方形分割为4个正方形，即可得到（2）对一切n6的自然数都成立. nk3个正方形.由（1）

例4求证用面值3分和5分的邮票可支付任何n(n≥８)分邮资．

证明显然当n=8,n=9,n=10时，可用3分和5分邮票构成上面邮资（n=8时，用一个3分邮票和一个5分邮票，n=9时，用3个3分邮票，n=10时，用2个5分邮票）．

下面假定k=n时命题正确，这时对于k=n+3，命题也正确，因为n分可用3分与5分邮票构成，再加上一个3分邮票，就使n3分邮资可用3分与5分邮票构成．由跳跃归纳法知命题对一切n≥８都成立．

下面我们介绍双归纳法，所谓双归纳法是所设命题涉及两个的自然数对(m,n),而不是一个单独的自然数n．

（2）反向数学归纳法

设P(n)是一个与正整数有关的命题，如果 ①P(n)对无限多个正整数n成立；

② 假设nk时，命题P(k)成立，则当nk1时命题P(k1)也成立，那么根据①②对一切正整

数n1时，P(n)成立．

例4 设a1,a2,L,an都是正数，证明：

a1a2Lanna1a2Lan n证：（1）先证明有无限多个正整数n，使命题成立.当n2m（对任意的mN,m1时），不等式成立， 对m用数学归纳法.

① 当m1时，即n2，因为(a1a2)20，所以② 假设mk时成立，即

a1a2a1a2即不等式成立. 2a1a2La2k2k2ka1a2La2k；

2kk1则当mk1时2a1a2La2ka2k1a2k2La2k1a1a2La2k2ka2k1a2k2La2k1 1a1a2La2ka2k1a2k2La2k1()kk2222

a1a2La2ka2k1a2k2La2k1.k122ka1a2La2k2ka2k1a2k2La2k1因此mk1时，不等式成立,故对于n2m（对任意的mN,m1时）命题成立.

a1a2Lakka1a2Lak，于是当nk1时，

kaaLak1a1a2Lak112aa2Lak1aaLak1k1有ka1a2Lak11 对此式两边12k1kk1aa2Lak1k1aaLak1同时k次方得a1a2Lak1(1成立，此为),即k1a1a2Lak112k1k1nk1时不等式成立.

aa2Lann由（1）、（2）知对一切自然数n(n1)都有1a1a2Lan.

n（2）假定nk时成立，即(3) 螺旋数学归纳法

设P(n)、Q(n)是两串与自然数n有关的命题，如果 ① 命题P(1)成立；

② 对任何自然数k，命题P(k)成立，则命题Q(k)成立；若命题Q(k)成立，则命题P(k1)成立. 那么根据①②对一切自然数n，命题P(n)与Q(n)都成立．

最后，我们给出跷跷板归纳法．

有两个与自然数有关的命题An与Bn，若 (1)A1成立；

(2)假设Ak成立，就推出Bk成立，假设Bk成立就推出Ak+1成立． 则对一切自然数n, An与Bn都成立．

A1 B1

A2 B2

Ak Bk

Ak+1 这里我们只给出一个例子说明上述归纳法． 例 已知

0a1,a11a,ana求证

1an1,n2

1an证明 令

1 1aAk:ak1， Bk:ak1 1a

(1)当n=1时，

1a21a1a

1a1a所以A1成立．

(2)

a211aa a11a1aa2(1a)211a

1a1a1a所以A2成立．

设Ak成立，则

ak1ak1a1a1aa1 11aak1

即Ｂk成立．

若Ｂk成立，则

ak111a21 a1aak1a1a即Ak+1成立．由跷跷板归纳法知，一切An和Bn都成立．

3m(m1)1,n2m1例5 已知数列an定义如下：an,求证：数列的前n项和为 2n2m3m,11S2m1m(4m23m1),S2mm(4m23m1).

221122证：将命题S2m1m(4m3m1)记作P(m)，将命题Smm(4m3m1) 记作Q(m).

221（1）当m1时，有S1a131(11)11(431),即P(1)成立.

212（2）证P(k)Q(k).假设P(k)成立，即有S2k1k(4k3k1)

211222于是S2kS2k1a2kk(4k3k1)3kk(4k3k1),故Q(k)成立.

2212（3）再证Q(k)P(k1).假设Q(k)成立，即有S2kk(4k3k1)

212于是S2k1S2ka2k1k(4k3k1)3k(k1)1

21111(k1)(4k23k1)3(k1)k(4k23k1)1(k1)(4k23k16k)(4k23k1)2222

1111(k1)(4k29k1)(4k1)(k1)(k1)(4k25k2)(k1)(4(k1)23(k1)1) 2222即P(k1)成立.

综上，由螺旋归纳法原理，命题P(m)、Q(m)对一切mN均成立.

（4）二重数学归纳法（两个变量）

设命题P(n,m)是与两个的自然数n,m有关的命题，如果

①P(1,m)对一切自然数m成立，P(n,1)对一切自然数n成立；

② 假设P(n1,m)和P(n,m1)成立时，可推证命题P(n1,m1)成立．则对所有自然数n,m，命题P(n,m)都成立.

例6 设f(m,n)满足f(m,n)f(m,n1)f(m1,n)，其中m,n是正整数，m,n2，且

m1f(1,n)f(m,1)1,(m,nN,m,n1),求证：f(m,n)Cmn2.

0m1证：（1）因为对于一切正整数n与m（m,n1），f(1,n)1C1n2,f(m,1)1Cmn1成立.即

此命题P(1,n),P(m,1)(m,nN,m,n1)为真.

mm1 （2）假设P(m1,n)和P(m,n1)成立，即f(m1,n)Cmn1，f(m,n1)Cmn1成立. mm1m则f(m1,n1)f(m1,n)f(m,n1)Cmn1+Cmn1=Cmn,则命题P(m1,n1)成立，由二重数

m1学归纳法知，对任意自然数m,n都有f(m,n)Cmn2.(m,n1)

（三）数学归纳法在高考中应用

例1 （05江西卷）已知数{an}的各项都是正数,且满足:a01,an1（1）证明anan12,nN; （2）求数列{an}的通项公式an. 解：（1）用数学归纳法证明：

1an(4an),nN. 213a0(4a0),∴a0a12，命题正确. 22112°假设n=k时有ak1ak2.则nk1时,akak1ak1(4ak1)ak(4ak)

22112(ak1ak)(ak1ak)(ak1ak)(ak1ak)(4ak1ak).

2211而ak1ak0.4ak1ak0,akak10.又ak1ak(4ak)[4(ak2)2]2.∴nk1221°当n=1时，a01,a1时命题正确.

由1°,2°知，对一切n∈N时有anan12.

方法二：用数学归纳法证明： 1°当n=1时，a01,a12°假设n=k时有ak113a0(4a0),∴0a0a12； 221ak2成立，令f(x)x(4x)，f(x)在[0，2]上单调递增，所以由假

2111ak1(4ak1)ak(4ak)2(42),也即当n=k+1 222时akak12成立，所以对一切nN,有akak12.

112（2）下面来求数列的通项：an1an(4an)[(an2)24],所以2(an12)(an2)

2212112211112222令bnan2,则bnbn(bn2)()2bnbn又bn=－1，所以 11()222222

nn11bn()21,即an2bn2()21.

22例2 （07湖北卷）已知m，n为正整数，

设有：f(ak1)f(ak)f(2),即

2n1n（I）用数学归纳法证明：当x1时，(1x)≥1mx；

m11m1m1（II）对于n≥6，已知1，求证，求证11，

22n3m3n32mmmmm1，2，L，n；

（III）求出满足等式34L(n2)(n3)的所有正整数n． 解：（Ⅰ）证：用数学归纳法证明：

（ⅰ）当m1时，原不等式成立；当m2时，左边12xx，右边12x，因为x以左边≥右边，原不等式成立；

（ⅱ）假设当mk时，不等式成立，即(1x)于是在不等式(1x)kknnnm22≥0，所

≥1kx，则当mk1时，∵x1，∴1x0，

≥1kx两边同乘以1x得

(1x)k·(1x)≥(1kx)(1x)1(k1)xkx2≥1(k1)x，所以(1x)k1≥1(k1)x．即当

mk1时，不等式也成立．

综合（ⅰ）（ⅱ）知，对一切正整数m，不等式都成立．

1m（Ⅱ）证：当n≥6，m≤n时，由（Ⅰ）得1≥10， n3n3于是1mm1≤1n3n3nnmnm11，2，L，n． 1，m12n3m（Ⅲ）解：由（Ⅱ）知，当n≥6时，

12n111111L1L11， nn3n3n32222nnn2nn2n13nnnn34L(n2)(n3)．即．即当n≥6时，不存在∴L1n3n3n3满足该等式的正整数n．故只需要讨论n1，2，3，4，5的情形：

当n1时，34，等式不成立；当n2时，345，等式成立；

当n3时，3456，等式成立；当n4时，3456为偶数，而7为奇数，故

333344444222nnn344474，等式不成立；当n5时，同n4的情形可分析出，等式不成立．

综上，所求的n只有n2，3．

解法二：（Ⅰ）证：当x0或m1时，原不等式中等号显然成立，下用数学归纳法证明： 当x1，且x0时，m≥2，(1x)1mx． ①

m（ⅰ）当m2时，左边12xx，右边12x，因为x0，所以x0，即左边右边，不等式①成立；

（ⅱ）假设当mk(k≥2)时，不等式①成立，即(1x)1kx，则当mk1时，因为x1，

k222所以1x0．又因为x0，k≥2，所以kx0．于是在不等式(1x)1kx两边同乘以1x得

k(1x)k·(1x)(1kx)(1x)1(k1)xkx21(k1)x，所以(1x)k11(k1)x．即当

mk1时，不等式①也成立．

综上所述，所证不等式成立．

mm1111（Ⅱ）当n≥6，m≤n时，∵1， ，而由（Ⅰ），∴1n32n32mm1mm110，∴11≥1≤1．

n3n3n3n32mnnnn（Ⅲ）假设存在正整数n0≥6使等式3040L(n02)nnn0(n03)n0成立，

34n02即有L1． ②

n3n3n300034n02L又由（Ⅱ）可得

n03n03n0300n01n01111111L1L11，与②式矛n0n3n3n32222000n0n0n0n0n0n0n0n0n0nn1盾．故当n≥6时，不存在满足该等式的正整数n．

下同解法1．

（四）数学归纳法在组合中应用

例1 有块边长为1的正方体木块，每块有一面为红色，其余5面为白色，把这块立方体放在一个88的国际象棋盘上（棋盘每格是边长为1的正方形，每格上恰放一块），然后将木块“转动”，转动的规则是将同一行（或同一列）的8个木块同时朝一个方向一起转动.问能否经过有限次转动，把所有木块的红色面都转到上面

解：将问题一般化，考虑n块木块放入nn的棋盘的问题，答案是肯定的.现用数学归纳法加以证明如下：

2n1时，结论显然成立.

设nk时，结论成立.那么nk1时，由归纳假设，左上角kk位置上可经过有限次转动，使每

个木块的红色面朝上.再将左方第一列的k1格木块逆时针（向外）旋转90，使该列前k个木块的红色面转到棋盘左侧.这时由归纳假设可经过有限次转动将右上角kk位置上每个小块的红色面朝上，且列的转动不影响第一列的木块，行的转动不改变第一列前k行红色面朝左的状态.完成上述转动后，再将第一列顺时针转动90，使前k行上的红色表面朝上.再将上方第一行朝后转动90，使第一行的红色面朝后方，同上可将下方k(k1)棋盘中所有方块的红色面转到上面，而不改变第一行红色面朝后状态.再将第一行转回使第一行的红色面朝上，于是所有(k1)(k1)棋盘中各小块的红色面都朝上，故nk1时结论成立.

因此，对任何正整数n结论成立，特别n8时结论成立.

例2 设S是2002个元素组成的集合，N为整数，满足0N22002ooo，证明：可将S的所有子集染

成黑色或白色，使下列条件成立：

(1) 任何两个白色子集的并集是白色； (2) 任何两个黑色子集的并集是黑色； (3) 恰好存在N个白色子集.

n证：考虑SSn中有n个元素的一般情形，这时N为满足0N2的整数，并且

设Sna1,a2,L,an，对n用数学归纳法证明.

当n1时，若N0，则将及a1都染成黑色，符合题目要求；若N1，则将染成黑色，a1染成白色，符合题目要求；若N2，则将及a1都染成白色，符合题目要求.设对n元集合Sn，及整数0N2，存在满足题目条件（1）（2）（3）的染色方法，考虑n1元集Sn1SnUan1.

n(1) 若0N2，则由归纳假设，存在一种染色方法将Sn的所有子集染成黑色或白色使得满足题目条件（1）（2）（3），这时再将Sn1中所含有an1的子集全染成黑色，于是仍满足题目条件.

(2) 若2N2nn1n，不妨设N2k(k1,2,L,2),则由归纳假设知存在Sn的子集的一种染色

nnn方法使满足题目条件（1）（2）且恰有k个子集被染成白色，再将Sn1中包含an1的所有子集（共2个）

染成白色，于是题目条件（1）（2）仍然满足，且一共有N2k个子集被染成白色，即条件（3）也满足，于是对Sn完成了归纳证明，特别取n2002便知题目结论成立.

n