离散数学─归纳与递归 南京大学计算机科学与技术系 数学归纳法 离散数学─归纳与递归 南京大学计算机科学与技术系
内容提要 数学归纳法 强数学归纳法 运用良序公理来证明
数学归纳法
数学归纳法（有效性） 良序公理 数学归纳法的有效性（归谬法） 正整数集合的非空子集都有一个最小元素 假设n P(n)不成立，则 n (P(n))成立. 令S={ n+ | P(n)}，S是非空子集. 根据良序公理，S有最小元素，记为m, m1 (m-1)S, 即P(m-1)成立. 根据归纳步骤，P(m)成立，即mS，矛盾. 因此，n P(n)成立.
数学归纳法（举例） Hk=1+1/2+…+1/k （k为正整数） 证明：H2n 1+n/2 （n为正整数） 基础步骤：P(1)为真， H2=1+1/2 归纳步骤：对任意正整数k, P(k) P(k+1). H2k+1 = H2k +1/(2k+1)+…+1/2k+1 (1+k/2)+2k(1/2k+1) =1+(1+k)/2 因此，对任意正整数n, P(n) 成立.
数学归纳法（举例） 猜测前n个奇数的求和公式，并证明之。 1=1 1+3=4 1+3+5=9 1+3+5+7=16 … 1+3+…+(2n-1)=n2（n为正整数） 运用数学归纳法证明（练习）
运用数学归纳法时犯的错误
强数学归纳法
强数学归纳法（一般形式） 设P(n)是与整数n有关的陈述， a和b是两个给定的整数，且a b. 如果能够证明下列陈述 则下列陈述成立 P(a), P(a +1), …, P(b). 对任意k b, P(a)… P(k)P(k+1) 则下列陈述成立 对任意n a, P(n).
强数学归纳法（有效性） { nZ | n a }是良序的 强数学归纳法的有效性（归谬法） 良序集：该集合的非空子集都有一个最小元素 假设n P(n)不成立，则 n (P(n))成立. 令S={ n | (na) P(n) }，S是非空子集. 根据良序公理，S有最小元素，记为m, m>b a, …, (m-1)S, 即P(a), …, P(m-1)成立, 其中 m-1 b. 根据归纳步骤，P(m)成立，即mS，矛盾. 因此，n P(n)成立.
强数学归纳法（举例） 任意整数n(n 2)可分解为（若干个）素数的乘积 用4分和5分就可以组成12分及以上的每种邮资. n = 2. P(12), P(13), P(14), P(15). 对任意k 15, P(12)… P(k)P(k+1)
（强）数学归纳法（举例） 对每个正整数n 4，n! 2n 基础步骤：P(4)为真，24 16 归纳步骤：对任意正整数k 4, P(k) P(k+1). (k+1)!= (k+1) k! (k+1) 2k 2k+1 因此，对任意正整数n 4, P(n) 成立.
运用良序公理来证明（举例） 设a是整数, d是正整数, 则存在唯一的整数q和r满足 证明 0 r < d a =dq+ r 令S={a-dq | 0a-dq ，qZ}，S非空. 非负整数集合具有良序性 S有最小元，记为r0 = a-dq0. 可证 0 r0 < d 唯一性证明， 0 r1 - r0 = d (q0-q1) d，因此，q1=q0
运用良序公理来证明（举例） 在循环赛胜果图中，若存在长度为m（m3）的回路，则必定存在长度为3的回路。 备注： ai aj 表示ai赢了aj 证明 设最短回路的长度为k //良序公理的保证 假设 k3 a1 a2 a3 … ak a1 若a3 a1, 存在长度为3的回路，矛盾。 若a1 a3, 存在长度为(k-1)的回路，矛盾。
Odd Pie Fights （奇数个馅饼的对抗） Placing an odd number of people in the plane, in such a way that every pair of people has a distinct distance between them. At a signal, each person will throw a pie at the closest other person. At least one person does not get hit with a pie？
作业 教材[4.1, 4.2] P209-214：18, 20, 63 P220-223：7, 12, 36（s和t都是整数）