nbhkdz.com冰点文库

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


数学归纳法
数学归纳法是用于证明与正整数 n 有关的数学命题的正确性的一种严格的推理方法.这种方法的原理 简单易懂, 在实际生活中都能找到它的影子, 多米诺骨牌、 蝴蝶效应都可以看做是数学归纳法的一种体现。 而在数学方面的应用上,它更显出了重要的地位,正因如此,在近年的高考试题,特别是压轴大题上,常 常运用数学归纳法来解题;在竞赛数学,数学归纳法更是在数列、组合等多方面

发挥着重要作用。 (一)数学归纳法的基本形式 (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 ,有

1 1 ? a an ?1 1 1 2? ? n ? 2? . an ?1 1 ? 1 an n n ?1
(1)求 a1 , a3 ; 解: (1)据条件得 2 ? (2)求数列 ? an ? 的通项 an .

? 1 1 1 ? 1 ? n(n ? 1) ? ? ? ? 2? an ?1 an ? an an ?1 ?



当 n ? 1 时,

由2?

?1 1 ? 1 1 1 2 2 1 2 8 ? 2 ? ? ? ? 2 ? ,即有 2 ? ? ? ? 2 ? ,解得 ? a1 ? .因为 a1 为正整数,故 a2 a1 4 a1 4 a1 3 7 ? a1 a2 ? ?1 1 ? 1 1 ? 6 ? ? ? ? 2 ? ,解得 8 ? a3 ? 10 ,所以 a3 ? 9 . a3 4 ? 4 a3 ?
2

a1 ? 1 .当 n ? 2 时,由 2 ?

(2)由 a1 ? 1 , a2 ? 4 , a3 ? 9 ,猜想: an ? n .下面用数学归纳法证明:
? 1 当 n ? 1 , 2 时,由(1)知 an ? n 均成立;
2

? 2 假设 n ? k (k ≥ 2) 成立, ak ? k ,则 n ? k ? 1 时由①得 2 ?
2

? 1 1 1 ? 1 ? k (k ? 1) ? 2 ? ? ? 2? 2 , ak ?1 ak ?1 ? k ?k

k 2 (k ? 1) k (k 2 ? k ? 1) (k ? 1) 2 1 2 ? 2 ? ak ?1 ? ? (k ? 1) ? 2 ? ak ?1 ? (k ? 1) 2 ? ,因为 k ≥ 2 时, k ? k ?1 k ?1 k ?1 k ?1

1

(k ? 1) 2 1 (k ? 1) ? (k ? 1) ? k (k ? 1)(k ? 2) ≥ 0 ,所以 2 ? ? 0, . k ?1≥1 ,所以 1? ? ? 0, . 1? k ?1 k ?1
2 2

又 ak ?1 ? N ,所以 (k ? 1) ≤ ak ?1 ≤ (k ? 1) ,故 ak ?1 ? (k ? 1) ,即 n ? k ? 1 时, an ? n 成立.
*
2 2

2

2

* 由 1 ? ,2 ? 知,对任意 n ? N , an ? n .
2

此题在证明时应注意,归纳奠基需验证的初始值又两个,即 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 且
3 2
?

? a3j ? (? a j ) ,求证: an ? n .
j ?1 j ?1

n

n

证: (1)当 n ? 1 时,因为 a1 ? a1 且 a1 ? 0 ,所以, a1 ? 1 ,命题成立; (2)假设 n ? k 时命题成立,即 a j ? j ( j ? 1, 2,? , k ) ,当 n ? k ? 1 时,因为

?a ? ?a
j ?1 3 j j ?1
3

k ?1

k

3 j

3 3 2 ? ak ?1 ? (? a j )2 ? ak ?1 , ? a 3 ? (? a j ) 2 ? (? a j ? ak ?1 ) 2 ? (? a j ) 2 ? 2ak ?1 ? a j ? ak ?1 j j ?1 j ?1 j ?1 j ?1 j ?1 j ?1

k

k ?1

k ?1

k

k

k

所以 ak ?1 ? 2ak ?1
k

? a j ? ak2?1 ,且 ak ?1 ? 0 ,于是 ak2?1 ? 2? a j ? ak ?1 ,因为 a j ? j ( j ? 1, 2,?, k ) ,
j ?1 j ?1

k

k



?a
j ?1

j

?

k (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) 成立.
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 , a2 ,? , an 都是正数,证明:

a1 ? a2 ? ? ? an n ? a1a2 ? an n
?

证: (1)先证明有无限多个正整数 n ,使命题成立.当 n ? 2m (对任意的 m ? N , m ? 1 时) ,不等式成立, 对 m 用数学归纳法. ① 当 m ? 1时,即 n ? 2 ,因为 ( a1 ? a2 ) ? 0 ,所以
2

a1 ? a2 ? a1a2 即不等式成立. 2

② 假设 m ? k 时成立,即

a1 ? a2 ? ? ? a2k 2
k

? 2k a1a2 ? a2k ;
2k

则当 m ? k ? 1时 2k ?1 a1a2 ?a2k ? a2k ?1a2k ?2 ?a2k ?1 ?

a1a2 ?a2k ? 2k a2k ?1a2k ?2 ?a2k?1

?

1 a1 ? a2 ? ? ? a2k a2k ?1 ? a2k ? 2 ? ? a2k ?1 ( ? ) 2 2 2k 2k a1 ? a2 ? ? ? a2k ? a2k ?1 ? a2k ? 2 ? ? a2k ?1 ? . 2k ?1
2k

a1a2 ? a2k ? 2k a2k ?1a2k ? 2 ? a2k ?1

?

因此 m ? k ? 1时,不等式成立,故对于 n ? 2m (对任意的 m ? N , m ? 1 时)命题成立.

?

a1 ? a2 ? ? ? ak k ? a1a2 ? ak ,于是当 n ? k ? 1 时, k a ? a ? ? ? ak ?1 a1 ? a2 ? ? ? ak ?1 ? 1 2 a1 ? a2 ? ? ? ak ?1 a ? a ? ? ? ak ?1 k ?1 有 k a1a2 ? ak ?1 ? 对此式两边 ? ? 1 2 k ?1 k k ?1 a ? a 2 ? ? ? ak ? 1 k ?1 a ? a ? ? ? ak ?1 同 时 k 次 方 得 a1a 2? ak ? 1? ( 1 成立,此为 ) , 即 k ?1 a1a2 ? ak ?1 ? 1 2 k ?1 k ?1 n ? k ? 1 时不等式成立. a ? a2 ? ? ? an n 由(1)(2)知对一切自然数 n(n ? 1) 都有 1 、 ? a1a2 ? an . n
(2)假定 n ? k 时成立,即
3

(3) 螺旋数学归纳法 设 P ( n) 、 Q(n) 是两串与自然数 n 有关的命题,如果 ① 命题 P (1) 成立; ② 对任何自然数 k ,命题 P(k ) 成立,则命题 Q(k ) 成立;若命题 Q(k ) 成立,则命题 P(k ? 1) 成立. 那么根据①②对一切自然数 n ,命题 P (n) 与 Q(n) 都成立. 例 5 已知数列 ? an ? 定义如下: an ? ?

?3m(m ? 1) ? 1, n ? 2m ? 1 ,求证:数列的前 n 项和为 2 n ? 2m ? 3m ,

1 1 S2 m?1 ? m(4m2 ? 3m ? 1), S2 m ? m(4m2 ? 3m ? 1) . 2 2 1 1 2 2 证:将命题 S2 m?1 ? m(4m ? 3m ? 1) 记作 P(m) ,将命题 Sm ? m(4m ? 3m ? 1) 记作 Q(m) . 2 2 1 (1)当 m ? 1时,有 S1 ? a1 ? 3 ?1? (1 ? 1) ? 1 ? 1 ? (4 ? 3 ? 1), 即 P (1) 成立. 2 1 2 (2)证 P(k ) ? Q(k ). 假设 P(k ) 成立,即有 S2 k ?1 ? k (4k ? 3k ? 1) 2 1 1 2 2 2 于是 S2 k ? S2 k ?1 ? a2 k ? k (4k ? 3k ? 1) ? 3k ? k (4k ? 3k ? 1), 故 Q(k ) 成立. 2 2 1 2 (3)再证 Q(k ) ? P(k ? 1). 假设 Q(k ) 成立,即有 S2 k ? k (4k ? 3k ? 1) 2 1 2 于是 S2 k ?1 ? S2 k ? a2 k ?1 ? k (4k ? 3k ? 1) ? 3k (k ? 1) ? 1 2 1 1 1 1 ? (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) 2 2 2 2 1 1 1 1 ? (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) 2 2 2 2
即 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) ? Cm? n?2 .

证: (1)因为对于一切正整数 n 与 m ( m, n ? 1 ) f (1, n) ? 1 ? C1? n ?2 , f (m,1) ? 1 ? Cm? n ?1 成立.即 ,
0

m ?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) ? Cm? n ?1,f (m, n ? 1) ? Cm? n ?1 成立.
m
m m ?1 m 则 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 江西卷)已知数 {a n }的各项都是正数, 且满足 : a0 ? 1, an ?1 ? (1)证明 an ? an?1 ? 2, n ? N ; 解: (1)用数学归纳法证明: 1°当 n=1 时, a0 ? 1, a1 ? (2)求数列 {a n } 的通项公式 an.

m ?1

1 an ? (4 ? an ), n ? N . 2

1 3 a0 (4 ? a0 ) ? , ∴ a0 ? a1 ? 2 ,命题正确. 2 2 1 1 2°假设 n=k 时有 a k ?1 ? a k ? 2. 则 n ? k ? 1时, ak ? ak ?1 ? ak ?1 (4 ? ak ?1 ) ? ak (4 ? ak ) 2 2 1 1 ? 2(ak ?1 ? ak ) ? (ak ?1 ? ak )(ak ?1 ? ak ) ? (ak ?1 ? ak )(4 ? ak ?1 ? ak ). 2 2 1 1 而 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 ? 1 2 2
时命题正确. 由 1°,2°知,对一切 n∈N 时有 a n ? a n ?1 ? 2. 方法二:用数学归纳法证明:

1 3 a0 (4 ? a0 ) ? , ∴ 0 ? a0 ? a1 ? 2 ; 2 2 1 2°假设 n=k 时有 a k ?1 ? a k ? 2 成立,令 f ( x) ? x(4 ? x) , f (x) 在[0,2]上单调递增,所以由假 2 1 1 1 设有: f (a k ?1 ) ? f (a k ) ? f (2), 即 a k ?1 (4 ? a k ?1 ) ? a k (4 ? a k ) ? ? 2 ? (4 ? 2), 也即当 n=k+1 2 2 2 时 a k ? a k ?1 ? 2 成立,所以对一切 n ? N , 有a k ? a k ?1 ? 2 . 1 1 (2)下面来求数列的通项: a n?1 ? a n (4 ? a n ) ? [?(a n ? 2) 2 ? 4], 所以 2(a n?1 ? 2) ? ?(a n ? 2) 2 2 2 1 2 1 1 2 2 1 1 2 2 1 2 令bn ? a n ? 2, 则bn ? ? bn?1 ? ? (? bn?2 ) ? ? ? ( ) bn?1 ? ? ? ?( )1? 2??? 2 bn 又 bn=-1,所以 2 2 2 2 2 2 1 n 1 n bn ? ?( ) 2 ?1 ,即an ? 2 ? bn ? 2 ? ( ) 2 ?1 . 2 2
1°当 n=1 时, a0 ? 1, a1 ?
2 n ?1 n

例 2 (07 湖北卷)已知 m n 为正整数, , (I)用数学归纳法证明:当 x ? ?1 时, (1 ? x) ≥ 1 ? mx ;
m

5

1 ? 1 m ? 1 m ? ? ? ? ?1? (II)对于 n≥ 6 ,已知 ?1 ? ? ? ,求证 ? 1 ? ? ? ,求证 ?1 ? ? ?? ? , 2 2 ? n?3? ? m?3? ? n?3? ?2?

m

m

m

m

m ? 1 2, ,n ; ,?
(III)求出满足等式 3 ? 4 ? ? ? (n ? 2) ? (n ? 3) 的所有正整数 n .
n n n m

解: (Ⅰ)证:用数学归纳法证明: (ⅰ)当 m ? 1时,原不等式成立;当 m ? 2 时,左边 ? 1 ? 2x ? x ,右边 ? 1 ? 2x ,因为 x
2 2

≥ 0 ,所

以左边≥ 右边,原不等式成立; (ⅱ) 假设当 m ? k 时, 不等式成立, (1 ? x) 即 于是在不等式 (1 ? x)
k k

≥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 ≥1 ? (k ? 1) x ,所以 (1? x )k ?1 ≥ 1? (k ? 1)x .即当 ·

m ? k ? 1时,不等式也成立.
综合(ⅰ) (ⅱ)知,对一切正整数 m ,不等式都成立.

1 ? m ? ? 0, (Ⅱ)证:当 n ≥ 6,m ≤ n 时,由(Ⅰ)得 ? 1 ? ? ≥1 ? n?3 ? n?3? m ? 1 ? ? ? 于是 ? 1 ? ? ≤ ?1 ? ? ? n?3? ? n?3?
n nm

m

n m ?? 1 ? ? ?1? ? ?? 1 ? ,? ? ? ? , m ? 1 2, ,n . ? ? ?2? ?? n ? 3 ? ? ? ?

m

(Ⅲ)解:由(Ⅱ)知,当 n ≥ 6 时,

1 ? ? 2 ? n ? 1 ?1? 1 ? ? ?1? ?1 ? ? ? ?1 ? ? ? ? ? ?1 ? ? ? ? ? ? ?? ? ? ? ? 1? n ? 1, 2 ? 2? 2 ? n?3? ? n?3? ? n?3? ? 2?
? n ? 2 ? ? n ?1 ? ? 3 ? n n n n ∴? ? ?? ? ?? ? ? ? ? 1 .即 3 ? 4 ? ? ? ( n ? 2) ? ( n ?3) .即当 n ≥ 6 时,不存在 ? n?3? ? n?3? ? n?3?
n n n

n

n

n

2

n

满足该等式的正整数 n .故只需要讨论 n ? 1 2,4,的情形: , 3, 5 当 n ? 1 时, 3 ? 4 ,等式不成立;当 n ? 2 时, 3 ? 4 ? 5 ,等式成立;
2 2 2

当 n ? 3 时, 3 ? 4 ? 5 ? 6 ,等式成立;当 n ? 4 时, 3 ? 4 ? 5 ? 6 为偶数,而 7 为奇数,故
3 3 3 3 4 4 4 4

4

34 ? 44 ? 54 ? 64 ? 74 ,等式不成立;当 n ? 5 时,同 n ? 4 的情形可分析出,等式不成立.

3 综上,所求的 n 只有 n ? 2,.
解法二: (Ⅰ)证:当 x ? 0 或 m ? 1时,原不等式中等号显然成立,下用数学归纳法证明:
6

当 x ? ?1 ,且 x ? 0 时, m ≥ 2 , (1 ? x) ? 1 ? mx .
m


2

(ⅰ)当 m ? 2 时,左边 ? 1 ? 2x ? x ,右边 ? 1 ? 2x ,因为 x ? 0 ,所以 x ? 0 ,即左边 ? 右边,不
2

等式①成立; (ⅱ)假设当 m ? k (k ≥ 2) 时,不等式①成立,即 (1 ? x) ? 1 ? kx ,则当 m ? k ? 1时,因为 x ? ?1 ,
k

所以 1 ? x ? 0 .又因为 x ? 0,k ≥ 2 ,所以 kx ? 0 .于是在不等式 (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时,不等式①也成立.
综上所述,所证不等式成立.
n m m ?? 1 ? 1 1 ? ? ?1? ? ? ,∴ ??1 ? (Ⅱ)当 n ≥ 6 , m ≤ n 时,∵ ? 1 ? , ? ? ? ,而由(Ⅰ) ? ? ? 2 ? n?3? ?? n ? 3 ? ? ? 2 ? ? ? m n m m ?? 1 ? m m ? 1 ? ? ?1? ? ? ? 0 ,∴?1 ? ?1 ? ? ≥1 ? ? ≤ ?? 1 ? ? ? ?? ? . n?3 ? n?3? ? n?3? ?? n ? 3 ? ? ? 2 ? ? ?

n

n

(Ⅲ)假设存在正整数 n0 ≥ 6 使等式 3 0 ? 4 0 ? ? ? (n0 ? 2)
n n

n0

? (n0 ? 3) n0 成立,

? 3 ? ? 4 ? ? n0 ? 2 ? 即有 ? ? ?? ? ?? ? ? ? ? 1. ? n0 ? 3 ? ? n0 ? 3 ? ? n0 ? 3 ? ? 3 ? ? 4 ? ? n0 ? 2 ? 又由(Ⅱ)可得 ? ? ?? ? ?? ? ? ? ? n0 ? 3 ? ? n0 ? 3 ? ? n0 ? 3 ? ? ? ? n ? n ?1 ? 1 ? ? ?1 ? 0 ? ? ?1 ? 0 ? ? ? ? ?1 ? ? ? n0 ? 3 ? ? n0 ? 3 ? ? n0 ? 3 ?
n0 n0 n0 n0 n0

n0

n0

n0


n0

?1? ?1? ? ? ? ?? ? ?2? ?2?

n0

n0 ?1

?? ?

1 1 ? 1 ? n0 ? 1 ,与②式矛 2 2

盾.故当 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 成黑色或白色,使下列条件成立: (1) 任何两个白色子集的并集是白色; (3) 恰好存在 N 个白色子集.
2002 ? ?

,证明:可将 S 的所有子集染

(2) 任何两个黑色子集的并集是黑色;

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

设 Sn ? ?a1 , a2 ,? , an ? ,对 n 用数学归纳法证明. 当 n ? 1 时, N ? 0 ,则将 ? 及 ? a1? 都染成黑色,符合题目要求; N ? 1,则将 ? 染成黑色,? a1? 若 若 染成白色,符合题目要求;若 N ? 2 ,则将 ? 及 ? a1? 都染成白色,符合题目要求.设对 n 元集合 S n ,及整
n 数 0 ? N ? 2 ,存在满足题目条件(1) (3)的染色方法,考虑 n ? 1元集 S n ?1 ? S n ? ?an ?1? . (2)

(1) 若 0 ? N ? 2 , 则由归纳假设, 存在一种染色方法将 S n 的所有子集染成黑色或白色使得满足题目
n

条件(1) (3) (2) ,这时再将 Sn?1 中所含有 an ?1 的子集全染成黑色,于是仍满足题目条件. (2) 若 2 ? N ? 2
n n ?1

,不妨设 N ? 2 ? k (k ? 1, 2,?, 2 ), 则由归纳假设知存在 S n 的子集的一种染色
n n

方法使满足题目条件(1) (2)且恰有 k 个子集被染成白色,再将 Sn?1 中包含 an ?1 的所有子集(共 2 个) 染成白色,于是题目条件(1) (2)仍然满足,且一共有 N ? 2 ? k 个子集被染成白色,即条件(3)也满
n

n

足,于是对 S n 完成了归纳证明,特别取 n ? 2002 便知题目结论成立.

8


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

高中数学竞赛专题讲座---数学归纳法在高考及竞赛中的应用_学科竞赛_高中教育_教育专区。数学归纳法数学归纳法是用于证明与正整数 n 有关的数学命题的正确性的一种...

高中数学竞赛培训专题讲座:数学归纳法

高中数学竞赛培训专题讲座:数学归纳法_学科竞赛_高中教育_教育专区。数学竞赛秘籍...?n . 2 2 (北京市高考数学试题) 5. 设实数 a1, a 2,..., a n 中...

高中数学竞赛专题讲座---数学归纳

高中数学竞赛专题讲座---数学归纳_高三数学_数学_高中教育_教育专区。高中数学竞赛...2 .(m, n ≥ 1) (三)数学归纳法在高考中应用 江西卷) 例 1 (05 江西...

高中数学竞赛专题讲座---同余理论及其应用(一)

高中数学竞赛专题讲座---同余理论及其应用(一)_学科竞赛_高中教育_教育专区。同余...同余理论在数学竞赛中的... 2页 2下载券 同余理论在数学竞赛中的... 2页 ...

高中数学竞赛讲座 17数学归纳法

高中数学竞赛讲座 17数学归纳法_学科竞赛_高中教育_...数学竞赛中占有很重要的地位. 1.数学归纳法的基本...

竞赛专题--数学归纳法的变着

百度文库 教育专区 高中教育 数学 高三数学上传文档支持以下设备:扫二维码下载 ...数学归纳法在竞赛中的应用 10页 2财富值 竞赛讲座 18-数学归纳法 4页 免费 ...

高中数学竞赛专题讲座之一:集合与函数

高中数学竞赛专题讲座之一:集合与函数_高一数学_数学_高中教育_教育专区。北京英才苑...故 12.解:考虑 M 的 n+2 元子集 P={n-l,n,n+1,…,2n}.P 中任...

高中数学竞赛专题讲座之数列

(2006 吉林预赛)如图所示,在杨辉三角中斜线上方的数所组成的数列 1,3,6,10,...高中数学竞赛专题讲座之... 6页 免费 数列与归纳法-高中数学竞... 94页 ...

高中数学竞赛专题讲座---竞赛中的数论问题

高中数学竞赛专题讲座---竞赛中的数论问题_学科竞赛_高中教育_教育专区。竞赛中的数论问题的思考方法一. 条件的增设 对于一道数论命题,我们往往要首先排除字母取零值...