第五讲：数学归纳法
数学归纳法是初等数论的基础，它刻画了整数的基本性质.虽然数学界仍然有一些数学家不认可数学归纳法，但是它在初等数论，组合数学，图论，离散数学的研究中被广泛运用，它在中学数学竞赛中的地位更是不言而喻，凡是遇到和自然数有关的命题都要考虑数学归纳法. 本讲我们主要介绍第一数学归纳法，第二数学归纳法，最小自然数原理，最大自然数原理以及它们的一些简单应用.这一部分内容大家可以参看《奥数教程》，《漫话数学归纳法》（苏淳著，中国科技大学出版社），《数列与数学归纳法》（单墫著，上海科技教育出版社）. 一．数学归纳法的基本形式
1. 第一数学归纳法：设 P(n) 是关于正整数 n 的命题，如果 ① P(1) 成立（奠基步）；
② 假设 P(k)（k为任意正整数） 成立，可以推出 P(k?1)成立（归纳递推步）， 那么，P(n) 对一切正整数 n 都成立.
注1：如果 P(n) 定义在 N 上，则 ① 中 “P(1) 成立”应由 “P(0) 成立”取代.
注2: 第一数学归纳法有如下变化形式：
跳跃数学归纳法：设 P(n) 是关于正整数 n 的命题，如果 ① P(1)，P(2)，…, P(l) 成立（奠基步）；
② 假设 P(k) 成立，可以推出 P(k?l)成立（归纳递推步）， 那么，P(n) 对一切正整数 n 都成立.
2. 第二数学归纳法：设 P(n) 是关于正整数 n 的命题，如果 ① P(1) 成立（奠基步）；
② 假设 n?k（k为任意正整数）时P(n)（1?n?k）成立，可以推出 P(k?1)成立 （归纳递推步），
那么，P(n) 对一切正整数 n 都成立.
二：例题选讲
1. 求证：?nk3?12k?14n(n?1)2
2. 设aan1?2,an?1?2?1a(n?N?)，求证：2?a1n?2?nn.
3. 设 n?5 ，证明：每一个正方形可以分为 n 个正方形.
4. 已知数列{an} 满足 a0?2,a1?10,an?2?6an?1?an， 求证：an可以写成两个整数的平方和.
1
5. 设 正数p1,p2,p3,...,p2n 满足 p1?p2?p3?...?p2n?1，
证明：p1log2p1?p2log2p2?p3log2p3?...?p2nlog2p2n??n.
(xlog2x?(1?x)log2(1?x)??1)
6. 求证：对任何正整数 n，方程 x2?y2?zn 都有正整数解. 7. 设
f(n) 定
义在正整数集上，且满足
f(1)?2,f(n?1)?(f(n))2?f(n)?1(n?N?).
求证：对所有正整数n?1，1?111112. 2n?1?f(1)?f(2)?...?f(n)?1?22n
8. 实数列 {an} 满足 ai?j?ai?aj，i,j?N.
证明：对任意 n?N，都有aa21?2?a3a3?...?nn?an.
2
9. 证明：(1) 对一切正整数 n ，1?11122?32?...?n2?2.( 用数学归纳法证明 ) (2 ) 证明：对一切正整数 n ，1?111122?32?...?n2?2?n.
10. 求证：1?123?133?...?1n3?3(n?N?).
11. 证明：存在正整数的无穷数列 {an}: a1?a2?a3?...,使得对所有自然数 n，
a221?a2?...?a2n 都是完全平方数.
12. 证明：任何多项式都可以表示成两个单调递增的多项式之差.
3
13. 设 x1,x2,x3,...是互不相同的正实数，证明：x1,x2,x3,... 是一个等比数列的充要条件是：
对所有整数 n(n?2)，都有 x1n?1x22n?xn?x21x?x22. 2k?1kxk?1x2?x1
14. 正整数数列 c1,c2,c3,... 满足下述条件：对任意正整数 m,n，若 1?m??n1ci，则存在
i?整数aanci1,a2,...,n,使得 m??. 问：对每个给定的 i?N*，ci 的最大值为多少？
i?1ai
15. 设 an1,a2,...,an 为正数，且 ?aj?1，又 0??1??2??3?...?n.
j?1证明：(?n?na(???)2jjaj)?(?)?1n.
j?1j?1?j4?1?n
16. 设 a?0，证明：a?2a?3a?...?na?a?1.
4
三：课后研讨题
1. 证明：对于一切自然数 n?3，都有 nn?1?(n?1)n. 2. 已知对一切 n?N*，an3n2n?0，且 ?aj?(?aj)j?1.
j?1证明：an?n.
3. 设 a?0,b?0, 且 11a?b?1.
证明：对一切自然数 n ，都有 (a?b)n?an?bn?22n?2n?14. 设 {a} 中的每一项都是正整数，并有 a1a2n?11n1?2;a2?7;?2?an?a?,n?3.
n?22证明：自从第二项开始，数列的各项都是奇数.
5. 设
k
是给定的正整数，r?k?12．记f(1()r)?f(?r)????r，f(l)(r)?f(f(l?1)(r)),l?2．（??x??表示不小于实数x的最小整数.）
证明：存在正整数m，使得f(m)(r)为一个整数．
6. 设实数 a1,a2,...,an 中任意两个的和非负，证明：对任意满足 x1?x2?...?xn?1 的
非负实数xx有 a221,2,...,xn, 1x1?a2x2?...?anxn?a1x1?a2x2?...?anx2n 成立.
5
r
7. 设 M?2n1?2n2?...?2ns，n1,n2,...,ns是互不相同的正整数， n1n2ns求证：22?22?...?22??1?2?M.
8. 证明：（1）对任何给定的自然数 n 和实数 x，都有
[x]?[x?12n?1n]?[x?n]?....?[x?n]?[nx]. ( [x] 表示不超过 x 的最大整数. )
(2) 对任何给定的自然数 n 和正实数 x，都有
[x]?[2x][2?....?nx]n?[nx].. ( [x] 表示不超过 x 的最大整数. )
9. 设 {an} 都是正实数列，且存在正的常数 c ，使得对所有 n，
a2?a2?a2212?...n?can?1.
证明：存在常数 b ，使得对所有 n，a1?a2?...?an?ban?1.
10. (Euler问题）证明：对任何自然数 n?3 ，数字 2n 都可以表示成 2n?7x2?y2
的形式，其中 x,y 都是奇数.
6