南京大学：《离散数学》课程教学资源（PPT课件讲稿）Lecture 08 归纳与递归

1 归纳与递归

归纳与递归 1

回顾 2 问题1：什么是（初等）数论？ ~研究整数的性质：整除、余数、同余算术 问题2：素数有哪些性质？ 素数基本定理 最大公约数 同余方程 欧拉定理/费马小定理

回顾 2 问题1：什么是(初等)数论？ - 研究整数的性质：整除、余数、同余算术 问题2：素数有哪些性质？ - 素数基本定理 - 最大公约数 - 同余方程 - 欧拉定理/费马小定理

本节提要 口归纳： 口数学归纳法与强数学归纳法 口运用良序公理来证明 口递归： 口递归定义 口结构归纳法与递归算法

本节提要  归纳： 数学归纳法与强数学归纳法 运用良序公理来证明  递归： 递归定义 结构归纳法与递归算法

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

⚫ 数学归纳法

数学归纳法（有效性） 口良序公理 口正整数集合的非空子集都有一个最小元素 口数学归纳法的有效性（归谬法) 口假设nPn)不成立，则3n(P)成立. 口令S={n∈Z+|PD},S是非空子集. 口根据良序公理，S有最小元素，记为m,m≠1 口(m-1)S,即Pm-1)成立. 口根据归纳步骤，P代m成立，即mS,矛盾. ▣因此，nPD成立

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

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

数学归纳法（举例） 口猜测前个奇数的求和公式，并证明之。 01=1 ▣1+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为正整数） 数学归纳法（举例）

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

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

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

⚫ 强数学归纳法

强数学归纳法（一般形式） 口设P(n)是与整数n有关的陈述，a和b是两个给定的 整数，且a≤b. 口如果能够证明下列陈述 口P(@,P(a+1),,P(b) 口对任意k≥b,P(@)A·AP()→P(k+1) 口则下列陈述成立 口对任意n≥，P(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). 强数学归纳法（一般形式）