南京大学：《离散数学 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) 成立