高中数学竞赛专题讲座---数学归纳法在高考及竞赛中的应用

数学归纳法
数学归纳法是用于证明与正整数
n
有关的数学命题的正确 性的一种严格的推理方法．这种方法的原理
简单易懂，在实际生活中都能找到它的影子，多米诺骨牌、蝴 蝶效应都可以看做是数学归纳法的一种体现。
而在数学方面的应用上，它更显出了重要的地位，正因如此 ，在近年的高考试题，特别是压轴大题上，常
常运用数学归纳法来解题；在竞赛数学，数学归纳法更是在 数列、组合等多方面发挥着重要作用。
（一）数学归纳法的基本形式
（1）第一数学归纳法
设
P(n)
是一个与正整数有关的命题，如果:
①当
n?n
0
（
n
0
?N
）时，
P(n)
成立；
②假设
n?k(k?n
0
,k?N)
成立，由此推得
n?k?1时，
P(n)
也成立，那么，根据①②对一切正整
数
n?n
0
时，
P(n)
成立．
*
例1 （07江西理22）设正整数数列
?
a
n
?
满足：
a
2
?4
，且对于任何
n?N
，有
11
?
aa< br>n?1
11
2??
n
?2?
．
a
n?1< br>1
?
1
a
n
nn?1
（1）求
a
1
，
a
3
； （2）求数列
?
a
n
?
的通项
a
n
． < br>解：（1）据条件得
2?
?
111
?
1
?n(n?1 )
?
??2?
① 当
n?1
时，
?
a
n?1
aaa
n?1
?
n
?
n
由2?
?
11
?
11
1221
28
?2
?
?
?
?2?
，即有
2????2?
，解得
?a< br>1
?
．因为
a
1
为正整数，故
a
2
a
1
4a
1
4a
1
37
?
a
1< br>a
2
?
?
11
?
11
?6
?
?
?
?2?
，解得
8?a
3
?10
，所以
a
3
?9
．
a
3
4
?
4a
3
?
2
a
1
?1
．当
n?2
时，由
2?
（2）由
a
1
?1
，
a
2
?4
，
a
3
?9
，猜想：
a
n
?n
．下面用 数学归纳法证明:
?
1当
n?1
，
2
时，由（1）知a
n
?n
均成立；
2
?
2假设
n?k(k≥ 2)
成立，
a
k
?k
，则
n?k?1
时由①得2?
2
?
111
?
1
?k(k?1)
?
2
??2?
,
?
2
a
k?1
kak
k ?1
??
k
2
(k?1)k(k
2
?k?1)(k?1)< br>2
1
2
?
2
?a
k?1
??(k?1)?< br>2
?a
k?1
?(k?1)
2
?
,因为
k≥ 2
时，
k?k?1k?1k?1k?1

1

(k ?1)
2
1
(k?1)?(k?1)?k(k?1)(k?2)≥0
，所以< br>2
?
?
0，1
?
．
k?1≥1
，所以
?
?
0，1
?
．
k?1
k?1
22
又
a
k?1
?N
，所以
(k?1)≤a
k?1
≤(k ?1)
,故
a
k?1
?(k?1)
，即
n?k?1
时，
a
n
?n
成立．
*
由1
?
，2?
知，对任意
n?N
，
a
n
?n
．
2
*
22
22
此题在证明时应注意，归纳奠基需验证的初始值又两个，即n?1
和
n?2
。
（2）第二数学归纳法
设
P(n)
是一个与正整数有关的命题，如果
① 当
n?n
0
（
n
0
?N
）时，
P(n)
成立；
② 假设
n?k(k?n
0
,k?N)
成立，由此推得
n? k?1
时，
P(n)
也成立，那么，根据①②对一切正
整数
n?n
0
时，
P(n)
成立．
例2 已知 对任意的
n?N,n?1,a
n
?0
且
32
?
?< br>a
j?1
n
3
j
?(
?
a
j
)
，求证：
a
n
?n
.
j?1
n
证： （1）当
n?1
时，因为
a
1
?a
1
且
a
1
?0
，所以，
a
1
?1
，命题成立；
（2）假设
n?k
时命题成立，即
a
j
?j(j?1,2,?,k)
,当
n?k?1
时，因为
?
a?
?
a
3
j
j?1j?1
k?1k
3
j
?a
3
k? 1
?(
?
a
j
)?a
2
j?1
2
k?1
，且
k
3
k?1
，
?
a
j?1k?1
3
j
2
?(
?
a
j
)?(?
a
j
?a
k?1
)?(
?
a
j)?2a
k?1
?
a
j
?a
k?1

222
j?1j?1j?1j?1
k?1kkk
所以
a
k
3
k?1
?2a
k?1
?
a
j
?a
j?1< br>k
a
k?1
?0
，于是
a
2
k?1
?2
?
a
j
?a
k?1
，因为
a
j
?j(j?1,2,?,k)
，
j?1
k
∴
?
a
j
?
j?1
k(k?1)
2
,从而
a
k?1?a
k?1
?k(k?1)?0
，解得
a
k?1
?k? 1
，
a
k
??k
（舍），即
n?k?1
时
2
命题成立.
由（1）、（2）知，对一切自然数
n(n?1)
都 有
a
n
?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)
成立．

2

例3 证明：任一正方形可以剖分成任意个数多于5个的正方形.
证：（1）对于
n?6,7,8
可按如图进行分割,
假设当
n?k(k?6)
成立,当
n?k?3
时，只要将其中一个正 方形分割为4个正方形，即可得到
（2）对一切
n?6
的自然数都成立.
n?k?3
个正方形.由（1）
（2）反向数学归纳法
设
P(n)
是一个与正整数有关的命题，如果
①
P(n)
对无限多个正整数
n
成立；
② 假设
n?k
时，命题
P(k)
成立，则当
n?k?1
时命题
P( k?1)
也成立，那么根据①②对一切正整
数
n?1
时，
P(n)
成立．
例4 设
a1
,a
2
,?,a
n
都是正数，证明：
a
1< br>?a
2
?
?
?a
n
n
?a
1
a
2
?
a
n

n
?
证：（1）先证明有 无限多个正整数
n
，使命题成立.当
n?2
m
（对任意的
m ?N,m?1
时），不等式成立，
对
m
用数学归纳法.
① 当< br>m?1
时，即
n?2
，因为
(a
1
?a
2< br>)?0
，所以
② 假设
m?k
时成立，即
2
a
1
?a
2
?a
1
a
2
即不等式成立.
2
a
1
?a
2
?
?
?a
2
k2
k
?
2
k
a
1
a
2
?a
2
k
；
2
k
则当
m?k?1
时< br>2
k?1
a
1
a
2
?a
2
k
?a
2
k
?1
a
2
k
?2
?a
2
k?1
?
2
k
a
1
a
2
?a< br>2
k
?
2
k
a
2
k
?1
a
2
k
?2
?a
2
k?1

?
1< br>a
1
?a
2
?
?
?a
2
k
a
2
k
?1
?a
2
k
?2
?
?a
2
k?1
(?)
kk
2222

a
1?a
2
?
?
?a
2
k
?a
2
k
?1
?a
2
k
?2
?
?a
2
k ?1
?.
2
k?1
?
?
a
1
a
2
?
a
2
k
?
2
k
a
2
k
?1
a
2
k
?2
?
a
2
k?1< br>因此
m?k?1
时，不等式成立,故对于
n?2
m
（对任意的
m?N,m?1
时）命题成立.
a
1
?a
2
?< br>?
?a
k
k
?a
1
a
2
?
a
k
，于是当
n?k?1
时，
k
a?a?
??a
k?1
a
1
?a
2
?
?
?ak?1
?
12
a?a
2
?
?
?a
k? 1
a?a?
?
?a
k?1
k?1
有
k
a< br>1
a
2
?
a
k?1
?
1
对此式两 边
??
12
k?1kk?1
a?a
2
?
?
?a
k?1
k?1
a?a?
?
?a
k?1
同时k
次方得
a
1
a
2
?
a
k?1
?(
1
成立，此为
)
,即
k?1
a
1
a
2
?
a
k?1
?
12
k?1k?1
n?k ?1
时不等式成立.
a?a
2
?
?
?a
n
n
由（1）、（2）知对一切自然数
n(n?1)
都有
1
?a1
a
2
?
a
n
.
n
（2）假定
n?k
时成立，即

3

(3) 螺旋数学归纳法
设
P(n)
、
Q(n)< br>是两串与自然数
n
有关的命题，如果
① 命题
P(1)
成立；
② 对任何自然数
k
，命题
P(k)
成立，则命题
Q(k)
成立；若命题
Q(k)
成立，则命题
P(k?1)
成立.
那么根据①②对一切自然数
n
，命题
P(n)
与
Q(n)
都成立．
例5 已知数列
?
a
n< br>?
定义如下：
a
n
?
?
?
3m(m?1)? 1,n?2m?1
,求证：数列的前
n
项和为
2
n?2m
?
3m,
11
S
2m?1
?m(4m
2
?3m?1 ),S
2m
?m(4m
2
?3m?1)
.
22
1 1
22
证：将命题
S
2m?1
?m(4m?3m?1)
记作
P(m)
，将命题
S
m
?m(4m?3m?1)
记作
Q(m)
.
22
1
（1）当
m?1
时，有< br>S
1
?a
1
?3?1?(1?1)?1?1?(4?3?1),
即
P(1)
成立.
2
1
2
（2）证
P(k)? Q(k).
假设
P(k)
成立，即有
S
2k?1
?k(4k ?3k?1)

2
11
222
于是
S
2k
?S
2k?1
?a
2k
?k(4k?3k?1)?3k?k(4k?3k?1 ),
故
Q(k)
成立.
22
1
2
（3）再证Q(k)?P(k?1).
假设
Q(k)
成立，即有
S
2k?k(4k?3k?1)

2
1
2
于是
S
2k ?1
?S
2k
?a
2k?1
?k(4k?3k?1)?3k(k?1 )?1

2
1111
?(k?1)(4k
2
?3k?1)? 3(k?1)k?(4k
2
?3k?1)?1?(k?1)(4k
2
?3k? 1?6k)?(4k
2
?3k?1)
2222
< br>1111
?(k?1)(4k
2
?9k?1)?(4k?1)(k?1)?(k ?1)(4k
2
?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
，且

4

m? 1
f(1,n)?f(m,1)?1,(m,n?N
?
,m,n?1)
,求证 ：
f(m,n)?C
m?n?2
.
证：（1）因为对于一切正整数
n
与
m
（
m,n?1
），
f(1,n)?1?C
1 ?n?2
,f(m,1)?1?C
m?n?1
成立.即
此命题
P(1 ,n),P(m,1)
(m,n?N,m,n?1)
为真.
（2）假设
P(m?1,n)和P(m,n?1)
成立，即
f(m?1,n)?C
m?n?1< br>，f(m,n?1)?C
m?n?1
成立.
mm?1m
则
f (m?1,n?1)?f(m?1,n)?f(m,n?1)?C
m?n?1
+C
m? n?1
=C
m?n
,则命题
P(m?1,n?1)
成立，由二重数< br>0m?1
?
mm?1
学归纳法知，对任意自然数
m,n
都有< br>f(m,n)?C
m?n?2
.(m,n?1)

（三）数学归纳法在高考中应用
例1 （05江西卷）已知数
{a
n
}的各项都是正数,且满足:
a
0
?1,a
n?1
?
（1 ）证明
a
n
?a
n?1
?2,n?N;
（2）求数列
{a
n
}
的通项公式
a
n
.
解：（1）用数学归纳法证明：
m?1
1
a
n
?(4?a
n
),n?N.

2
13
a
0
(4?a
0
)?,
∴
a
0
?a
1
?2
，命题正确.
22
11
2°假设
n
=
k
时有
a
k?1
?a
k?2.
则
n?k?1时,a
k
?a
k?1
?a
k?1
(4?a
k?1
)?a
k
(4?a
k
)
22
11
?2(a
k?1
?a
k
)?(a< br>k?1
?a
k
)(a
k?1
?a
k
)?(a
k?1
?a
k
)(4?a
k?1
?a
k
) .

22
11
而
a
k?1
?a
k
?0.4?a
k?1
?a
k
?0,?a
k
?a
k? 1
?0.
又
a
k?1
?a
k
(4?a
k< br>)?[4?(a
k
?2)
2
]?2.
∴
n?k?1< br>22
1°当n=1时，
a
0
?1,a
1
?
时 命题正确.
由1°,2°知，对一切n∈N时有
a
n
?a
n?1< br>?2.

方法二：用数学归纳法证明：
13
a
0
( 4?a
0
)?,
∴
0?a
0
?a
1
?2< br>；
22
1
2°假设
n
=
k
时有
a
k?1
?a
k
?2
成立，令
f(x)?x(4?x)
，
f(x)
在[0，2]上单调递增，所以由假
2
111
设有：< br>f(a
k?1
)?f(a
k
)?f(2),
即
ak?1
(4?a
k?1
)?a
k
(4?a
k
) ??2?(4?2),
也即当n=k+1
222
时
a
k
? a
k?1
?2
成立，所以对一切
n?N,有a
k
?a
k?1
?2
.
11
（2）下面来求数列的通项：
a
n? 1
?a
n
(4?a
n
)?[?(a
n
?2)
2
?4],
所以
2(a
n?1
?2)??(a
n
?2)
2

22
1
2
11
22
11
22
1
1?2?
?
?22
令
b
n
?a< br>n
?2,
则
b
n
??b
n
??(?b)?? ?()b?
?
??()b
n
又b
n
=－1，所以
?1n?2n?1
222222

1
n
1
n
b
n
??()
2?1
,即a
n
?2?b
n
?2?()
2?1
.
22
1°当n=1时，
a
0
?1,a
1
?
2n?1n
例2 （07湖北卷）已知
m，n
为正整数，
（I）用数学归纳法证明：当
x??1
时，
(1?x)≥1?mx
；
m

5

1
?
1m
?
1m
?
??
??
1
?
?1??1??
（II）对于n≥6
，已知
?
1?
，求证，求证
???
????，
22
?
n?3
??
m?3
?
?
n? 3
??
2
?
mm
mm
m?1，2，?，n
； （III）求出满足等式
3?4???(n?2)?(n?3)
的所有正整数
n< br>．
解：（Ⅰ）证：用数学归纳法证明：
（ⅰ）当
m?1
时，原不等 式成立；当
m?2
时，左边
?1?2x?x
，右边
?1?2x
，因为
x
以左边
≥
右边，原不等式成立；
（ⅱ）假设当
m?k
时，不等式成立，即
(1?x)
于是在不等式
(1?x)
k< br>k
nnnm
22
≥
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?kx
2
≥< br>1?(k?1)x
，所以
(1?x)
k?1
≥
1?(k?1) x
．即当
m?k?1
时，不等式也成立．
综合（ⅰ）（ⅱ）知，对一切正整数
m
，不等式都成立．
1
?
m
?
≥
1??0
， （Ⅱ）证：当
n
≥
6，m
≤
n
时，由（Ⅰ）得
?
1?
?< br>n?3n?3
??
于是
?
1?
m
?
?
m
?
1
??
≤
1?
???
n?3
??< br>n?3
?
nnm
nm
?
?
1
?
?< br>?
1
?
?
?
?
1?
，2，?，n
．
?
?
?
??
，
m?1
n?32
?
?
??
?
?
?
?
m
（Ⅲ）解：由（Ⅱ）知，当n
≥
6
时，
1
??
2
?
n
?
1
?
1
?
1
???
1
?
1?? 1??
?
?1????
?
??1??1
，
??????? ???
n
n?3n?3n?32222
??????????
?
n? 2
??
n?1
??
3
?
nnnn
∴
???
?
??1
3
?
4
???
(
n?< br>2)
?
(
n?
3)
．即
．即当
n
≥
6
时，不存在
?????
?
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
为奇数，故
33334444
222
n nn
nnn
2
n
4
3
4
?4
4
? 5
4
?6
4
?7
4
，等式不成立；当
n?5
时，同
n?4
的情形可分析出，等式不成立．
3
． 综上，所求的
n
只有
n?2，
解法二：（Ⅰ）证：当
x?0
或
m?1< br>时，原不等式中等号显然成立，下用数学归纳法证明：

6

当
x??1
，且
x?0
时，
m
≥
2
，(1?x)?1?mx
． ①
m
（ⅰ）当
m?2
时，左边< br>?1?2x?x
，右边
?1?2x
，因为
x?0
，所以
x?0
，即左边
?
右边，不
等式①成立；
（ⅱ）假设当
m?k(k
≥
2)
时，不等式①成立，即
(1?x)?1?kx
，则 当
m?k?1
时，因为
x??1
，
k
22
所以1?x?0
．又因为
x?0，k
≥
2
，所以
kx?0< br>．于是在不等式
(1?x)?1?kx
两边同乘以
1?x
得
2
k
(1?x)
k
·(1?x)?(1?kx)(1?x)?1?(k?1) x?kx
2
?1?(k?1)x
，所以
(1?x
k
)
?1
?1?k(?1)x
．即当
m?k?1
时，不等式①也成立．
综上所述，所证不等式成立．
mm
?
?
1
?
1< br>1
?
?
?
1
?
?
（Ⅱ）当
n
≥
6
，
m
≤
n
时，
∵
?
1?< br>，
?
?
，
∴
?
?
1?
?
?
?
??
，而由（Ⅰ）
n?32
??
?
?
n?3
?
?
?
?
2
?
?
mm
?< br>?
1
?
m
m
?
1
?
?
?< br>1
?
?
?
?0
，
∴
?
1?
?
1?
?
≥
1?
?
≤
?
?
1?< br>?
?
?
??
．
n?3n?3
n?3n?3
??
???
??
?
?
?
?
2
?
m
n
n
n
n
（Ⅲ）假设存在正整数
n
0
≥< br>6
使等式
3
0
?4
0
???(n
0
?2)
nnn
0
?(n
0
?3)
n
0
成立 ，
?
3
??
4
??
n
0
?2
?
即有
??
?
??
?
?
?
??
?1
． ②
n?3n?3n?3
?
0
??
0
??< br>0
?
?
3
??
4
??
n
0
?2
?
??
?
?
又由（Ⅱ）可得
??????
< br>?
n
0
?3
??
n
0
?3
??n
0
?3
?
???
n
?
n?1
?1
?
?
?
1?
0
?
?
?
1?
0
?
?
?1?
???
?
n
0
?3
??
n
0
?3
??
n
0
?3
?< br>n
0
n
0
n
0
0
?
1
??
1
?
?
??
?
??
?
2
??2
?
n
0
n
0
n
0
n
0n
0
n
0
nn
0
?1
?
?
?
11
?1?
n
0
?1
，与②式矛
22
盾． 故当
n
≥
6
时，不存在满足该等式的正整数
n
．
下同解法1．
（四）数学归纳法在组合中应用
例1 有64块边长为1的正方体 木块，每块有一面为红色，其余5面为白色，把这64块立方体放在
一个
8?8
的国际 象棋盘上（棋盘每格是边长为1的正方形，每格上恰放一块），然后将木块“转动”，转动
的规则是将同 一行（或同一列）的8个木块同时朝一个方向一起转动.问能否经过有限次转动，把所有木
块的红色面都 转到上面？
解：将问题一般化，考虑
n
块木块放入
n?n
的棋盘的 问题，答案是肯定的.现用数学归纳法加以证明
如下：
2
n?1
时，结论显然成立.
设
n?k
时，结论成立.那 么
n?k?1
时，由归纳假设，左上角
k?k
位置上可经过有限次转动，使每

7

个木块的红色面朝上.再将左方第一列的
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?2
2002
??
，证明：可将
S
的所有子集染
成 黑色或白色，使下列条件成立：
(1) 任何两个白色子集的并集是白色； (2) 任何两个黑色子集的并集是黑色；
(3) 恰好存在
N
个白色子集.
n< br>证：考虑
S?S
n
中有
n
个元素的一般情形，这时
N
为满足
0?N?2
的整数，并且
设
S
n
?
?
a
1
,a
2
,?,a
n
?
，对
n
用数学归纳法证明.
当
n?1
时，若
N?0
，则将< br>?
及
?
a
1
?
都染成黑色，符合题目要求；若
N?1
，则将
?
染成黑色，
?
a
1
?
染 成白色，符合题目要求；若
N?2
，则将
?
及
?
a
1
?
都染成白色，符合题目要求.设对
n
元集合
S
n
，及整
n
数
0?N?2
，存在满足题目条件（1）（2）（3）的染色方法 ，考虑
n?1
元集
S
n?1
?S
n
?
?< br>a
n?1
?
.
(1) 若
0?N?2
，则由归纳假 设，存在一种染色方法将
S
n
的所有子集染成黑色或白色使得满足题目
条件（ 1）（2）（3），这时再将
S
n?1
中所含有
a
n?1
的 子集全染成黑色，于是仍满足题目条件.
(2) 若
2?N?2
nn?1
n
，不妨设
N?2?k(k?1,2,?,2),
则由归纳假设知存在
S
n
的子集的一种染色
n
nn
方法使满足题目条件（1）（2）且恰有
k
个子集被染成白色，再将
S
n?1
中包含
a
n?1的所有子集（共
2
个）
染成白色，于是题目条件（1）（2）仍然满足，且一共有
N?2?k
个子集被染成白色，即条件（3）也满
足，于是对
S
n< br>完成了归纳证明，特别取
n?2002
便知题目结论成立.
n

8