归纳与递归 离散数学一归纳与递归 南京大学计算机科学与技术系
归纳与递归 离散数学─归纳与递归 南京大学计算机科学与技术系
内容提要 ·归纳 ·数学归纳法 ·强数学归纳法 ●运用良序公理来证明 ·递归 ●递归定义 ·结构归纳法 。递归算法
内容提要 归纳 数学归纳法 强数学归纳法 运用良序公理来证明 递归 递归定义 结构归纳法 递归算法
数学归纳法 ●证明目标 ●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, m1 (m-1)S, 即P(m-1)成立. 根据归纳步骤，P(m)成立，即mS，矛盾. 因此，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)
强数学归纳法