数学归纳法离散数学一归纳与递归
数学归纳法 离散数学─归纳与递归
内容提要数学归纳法强数学归纳法运用良序公理来证明
内容提要 ⚫ 数学归纳法 ⚫ 强数学归纳法 ⚫ 运用良序公理来证明
数学归纳法
数学归纳法
数学归纳法（有效性）良序公理正整数集合的非空子集都有一个最小元素数学归纳法的有效性（归谬法）假设VnP(n)不成立，则日n(一P(n))成立令S={neZ+|→P(n)}，S是非空子集根据良序公理，S有最小元素，记为m,m1(m-1)S, 即 P(m-1)成立,根据归纳步骤，P(m)成立，即mεS，矛盾.因此，nP(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)成立
数学归纳法（举例）《（k为正整数）Hk=1+1/2+...+1/k（n为正整数）证明：H,"≥1+n/2基础步骤：P(1)为真，H,=1+1/2归纳步骤：对任意正整数k,P(k)=P(k+1)H,k+1 = H,k +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) 成立