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, m1 (m-1)S, 即P(m-1)成立. 根据归纳步骤，P(m)成立，即mS，矛盾. 因此，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). 强数学归纳法（一般形式）