1、数学归纳法离散数学归纳与递归南京大学计算机科学与技术系内容提要 数学归纳法 强数学归纳法 运用良序公理来证明数学归纳法数学归纳法（有效性） 良序公理 正整数集合的非空子集都有一个最小元素 数学归纳法的有效性（归谬法） 假设 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)成立.数学归纳法（举例） Hk=1+1/2+1/k （k为正整数） 证明：H2n 1+n/2 （n为正整数） 基础步骤：P(1)为真， H
2、2=1+1/2 归纳步骤：对任意正整数k, P(k) P(k+1). H2k+1 = H2k +1/(2k+1)+1/2k+1(1+k/2)+2k(1/2k+1) =1+(1+k)/2 因此，对任意正整数n, P(n) 成立. 数学归纳法（举例） 猜测前n个奇数的求和公式，并证明之。 1=1 1+3=4 1+3+5=9 1+3+5+7=16 1+3+(2n-1)=n2（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).强数学归纳法（有效性） nZ | n a 是良序的 良序集：该集合的非空子集都有一个最小元素 强数学归纳法的有效性（归谬法） 假设 n P(n)不成立 ，则 n (P(n)成立. 令S= n | (na) P(n) ，S是非空子集. 根据良序公理，S有最小元素，记为m, mb a, , (m-1)S, 即P(a), , P(m-1)成立, 其中 m-1 b. 根据归纳步骤，P(m)成立，即mS，矛盾. 因此， n P(n)成立.
