南京大学：《离散数学 Discrete Mathmatics》课程教学资源（课件讲稿，2018）集合论——第9章 归纳与递归

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

强数学归纳法（有效性） ●{n∈Z|n≥a}是良序的 。良序集：该集合的非空子集都有一个最小元素 ·数学归纳法的有效性（归谬法) ●假设VnPm)不成立，则3n(-P(m)成立. 。令S={n∈Z|(n2m)nP(m)},S是非空子集， 。根据良序公理，S有最小元素，记为m,m>a 。a,,(m-1)eS,即P(@,,P(m-1)成立. 。根据归纳步骤，P(m)成立，即m廷S,矛盾、 。因此，HnP(n)成立

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

强数学归纳法（举例) ·任意整数n(n≥2)可分解为（若干个)素数的乘积 ●n=2. ●考察n+1. ·用4分和5分就可以组成12分及以上的每种邮资. P(12),P(13),P(14),P(15) ●对任意k≥15，P(12)Λ.·∧P()→P(k+1)

强数学归纳法（举例）  任意整数n(n 2)可分解为（若干个）素数的乘积  n = 2.  考察 n+1.  用4分和5分就可以组成12分及以上的每种邮资.  P(12), P(13), P(14), P(15).  对任意k 15, P(12)… P(k)P(k+1)

(强)数学归纳法（举例） ·对每个正整数n≥4，n!>2n 。基础步骤：P(4)为真，24>16 ·归纳步骤：对任意正整数k≥4，P(→P(k+1) (k+1)=(k+1)k:>(k+1)2k>2k+1 。因此，对任意正整数n≥4，P(m)成立

（强）数学归纳法（举例）  对每个正整数n  4，n!  2 n  基础步骤：P(4)为真，24 16  归纳步骤：对任意正整数k 4, P(k) P(k+1). (k+1)!= (k+1) k!  (k+1) 2 k  2 k+1  因此，对任意正整数n  4, P(n) 成立