南京大学：《离散数学 Discrete Mathmatics》课程教学资源（课件讲稿，2018）集合论——第9章 归纳与递归

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

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

内容提要 ·归纳 ·数学归纳法 ·强数学归纳法 ●运用良序公理来证明 ·递归 ●递归定义 ·结构归纳法 。递归算法

内容提要  归纳  数学归纳法  强数学归纳法  运用良序公理来证明  递归  递归定义  结构归纳法  递归算法

数学归纳法 ●证明目标 ●VnP(n) n的论域为正整数集合 。证明框架 。基础步骤：P(1)为真 ●归纳步骤：证明k(P(k)→Pk+1) 。/对任意正整数k,给出P()上P(k+1)的论证步骤. ●… 。因此，对任意正整数n,P(n)成立.∥即：nP(n)

数学归纳法 

数学归纳法（有效性） ●良序公理 。正整数集合的非空子集都有一个最小元素 ·数学归纳法的有效性（归谬法) ●假设VnP(n)不成立，则n(P(n)成立， 。令S={neZ|P(nm)},S是非空子集， 。根据良序公理，S有最小元素，记为m,≠1 ●(m-1)eS,即P(m-1)成立. ●根据归纳步骤，P(m成立，即mS,矛盾 。因此，HnP(n)成立

数学归纳法（有效性）  良序公理  正整数集合的非空子集都有一个最小元素  数学归纳法的有效性（归谬法）  假设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)成立

数学归纳法（举例） 。Hk=1+1/2+..+1/k(k为正整数) ● 证明：H,"≥1+n/2(n为正整数) 。基础步骤：P(1)为真，H2=1+1/2 。归纳步骤：对任意正整数k,P)→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)成立

数学归纳法（举例）  Hk=1+1/2+…+1/k （k为正整数）  证明：H2 n 1+n/2 （n为正整数）  基础步骤：P(1)为真， H2=1+1/2  归纳步骤：对任意正整数k, P(k) P(k+1). H2 k+1 = H2 k +1/(2k+1)+…+1/2k+1 (1+k/2)+2k (1/2k+1) =1+(1+k)/2  因此，对任意正整数n, P(n) 成立

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

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

运用数学归纳法时犯的错误 平面上任何一组相互间不平行的直线必相交于一点. ●基础步骤：P(2)为真 。归纳步骤：对任意正整数k,P()上Pk+1) 。前k条交于P1 。后k条交于P2 0P1=P2

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

数学归纳法证明时常见错误 例1：任意个人，他们一定全部在同一天出生. 错误证明： o Basis:当n=1时，只有一个人，命题显然成立； IH:假设任意k个人，他们全部在同一天出生，则： oI.S.:当有k+1个人时（编号为1,2，…，k,k+1),根据 归纳假设，第1人至第k人（共k个人)一定在同一天出 生；第2至第k+1人（共k个人)也一定在同一天出生。 因此，这k+1人全部在同一天出生。根据数学归纳法， 命题成立.口 o归纳基础错误：P(1)rP(2)川

数学归纳法证明时常见错误

数学归纳法证明时常见错误 例2：证明∑12i-1=n2 错误证明： Basis:当n=1时，=12i-1=12命题成立； I.H.:假设当n=k时∑12i-1=k2成立，则： 。I.S.:根据等差数列的求和公式，∑12i-1=1+3+ 5+…+2(k+1)-1=1+2k+)-k+=(k+1)2。 2 根据数学归纳法，命题成立.口 o归纳过程错误：未证明P(k)→P(k+1)!

数学归纳法证明时常见错误

强数学归纳法 ●证明目标 ●廿nP(n)n的论域为正整数集合 ·证明框架 。基础步骤：P(1)为真 ●归纳步骤：证明k(P(1)A·AP(k)→P(k+1) 。/对任意正整数k,给出P(1),,P(上P(k+1)的论证步骤 ●… 。因此，对任意正整数n,P(n)成立.∥即：廿nP(n)

强数学归纳法 