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)成立. 数学归纳法（有效性）