离散数学─归纳与递归 南京大学计算机科学与技术系

Presentation on theme: "离散数学─归纳与递归 南京大学计算机科学与技术系"— Presentation transcript:

1 离散数学─归纳与递归 南京大学计算机科学与技术系
数学归纳法 离散数学─归纳与递归 南京大学计算机科学与技术系

2 内容提要 数学归纳法 强数学归纳法 运用良序公理来证明

3 数学归纳法

4 数学归纳法（有效性） 良序公理 数学归纳法的有效性（归谬法） 正整数集合的非空子集都有一个最小元素
假设n P(n)不成立，则 n (P(n))成立. 令S={ n+ | P(n)}，S是非空子集. 根据良序公理，S有最小元素，记为m, m1 (m-1)S, 即P(m-1)成立. 根据归纳步骤，P(m)成立，即mS，矛盾. 因此，n P(n)成立.

5 数学归纳法（举例） 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) 成立.

6 数学归纳法（举例） 猜测前n个奇数的求和公式，并证明之。 1=1 1+3=4 1+3+5=9 1+3+5+7=16 …
1+3+…+(2n-1)=n2（n为正整数） 运用数学归纳法证明（练习）

7 运用数学归纳法时犯的错误

8 强数学归纳法

9 强数学归纳法（一般形式） 设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).

10 强数学归纳法（有效性） { nZ | n  a }是良序的 强数学归纳法的有效性（归谬法） 良序集：该集合的非空子集都有一个最小元素
假设n P(n)不成立，则 n (P(n))成立. 令S={ n | (na) P(n) }，S是非空子集. 根据良序公理，S有最小元素，记为m, m>b a, …, (m-1)S, 即P(a), …, P(m-1)成立, 其中 m-1  b. 根据归纳步骤，P(m)成立，即mS，矛盾. 因此，n P(n)成立.

11 强数学归纳法（举例） 任意整数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)

12 （强）数学归纳法（举例） 对每个正整数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) 成立.

13 运用良序公理来证明（举例） 设a是整数, d是正整数, 则存在唯一的整数q和r满足 证明 0  r < d a =dq+ r
令S={a-dq | 0a-dq ，qZ}，S非空. 非负整数集合具有良序性 S有最小元，记为r0 = a-dq0. 可证 0  r0 < d 唯一性证明， 0  r1 - r0 = d (q0-q1)  d，因此，q1=q0

14 运用良序公理来证明（举例） 在循环赛胜果图中，若存在长度为m（m3）的回路，则必定存在长度为3的回路。
备注： ai  aj 表示ai赢了aj 证明 设最短回路的长度为k //良序公理的保证 假设 k3 a1  a2  a3 …  ak a1 若a3 a1, 存在长度为3的回路，矛盾。 若a1  a3, 存在长度为(k-1)的回路，矛盾。

15 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？

16 作业 教材[4.1, 4.2] P ：18, 20, 63 P ：7, 12, 36（s和t都是整数）