归纳与递归
归纳与递归 1
回顾内容1：基础概念数论研究整数的性质：整除、余数、同余算术内容2：素数和最大公约数大于1自然数可以写成唯一的素数乘积形式求最大公约数：辗转相除/减法：最大公约数gcd(a,b）一定是a和b的线性组合内容3：同余方程与费马小定理两两互素作模，一元线性同余方程解唯一- (a,n)=1, a(n)模n余1
回顾 2 内容1：基础概念 - 数论研究整数的性质：整除、余数、同余算术 内容2：素数和最大公约数 - 大于1自然数可以写成唯一的素数乘积形式 - 求最大公约数：辗转相除/减法 - 最大公约数gcd(a, b)一定是a和b的线性组合 内容3：同余方程与费马小定理 - 两两互素作模，一元线性同余方程解唯一 - (a,n)=1，𝒂 φ(𝒏)模n余1
本节提要口归纳:口数学归纳法与强数学归纳法口运用良序公理来证明口递归：口递归定义口结构归纳法与递归算法
本节提要 归纳： 数学归纳法与强数学归纳法 运用良序公理来证明 递归： 递归定义 结构归纳法与递归算法
数学归纳法证明目标//n的论域为正整数集合Vn P(n)证明框架基础步骤：P(1)为真归纳步骤：证明Vk(P(k)→P(k+1))//对任意正整数k，给出P(k)卜P(k+1)的论证步骤因此，对任意正整数n,P(n)成立.// 即：VnP(n)
⚫ 数学归纳法
数学归纳法（有效性）口良序公理口正整数集合的非空子集都有一个最小元素数学归纳法的有效性（归谬法）口假设VnP(n)不成立，则日n(-P(n)成立口令S=（neZ+I一P(n))，S是非空子集，口根据良序公理，S有最小元素，记为m,㎡1口 (m-1)S,即 P(m-1)成立口根据归纳步骤，Pm)成立，即mS，矛盾.口因此，VnP(n)成立
良序公理 正整数集合的非空子集都有一个最小元素 数学归纳法的有效性（归谬法） 假设nP(n)不成立，则n (P(n))成立. 令S={ n+ | P(n)}，S是非空子集. 根据良序公理，S有最小元素，记为m, m1 (m-1)S, 即P(m-1)成立. 根据归纳步骤，P(m)成立，即mS，矛盾. 因此，nP(n)成立. 数学归纳法（有效性）