数学归纳法-南京大学.pdf

数学归纳法 离散数学─归纳与递归 南京大学计算机科学与技术系 内容提要  数学归纳法  强数学归纳法  运用良序公理来证明 数学归纳法  数学归纳法（有效性）  良序公理  正整数集合的非空子集都有一个最小元素  数学归纳法的有效性（归谬法）  假设∀n P(n)不成立，则∃n (¬P(n))成立. +  令S={ n ∈Ζ | ¬P(n)}，S是非空子集.  根据良序公理，S有最小元素，记为m, m≠1  (m-1)∉S, 即P(m-1)成立.  根据归纳步骤，P(m)成立，即m ∉S，矛盾.  因此，∀n P(n)成立. 数学归纳法（举例）  H =1+1/2+…+1/k （k为正整数） k  证明：H2n ≥1+n/2 （n为正整数）  基础步骤：P(1)为真，H =1+1/2 2  归纳步骤：对任意正整数k, P(k) ⇒P(k+1). k+1 k k k+1 H2 = H2 +1/(2 +1)+…+1/2 k k+1 ≥(1+k/2)+2 (1/2 ) =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). 强数学归纳法（有效性）  { n ∈Z | n ≥a }是良序的  良序集：该集合的非空子集都有一个最小元素  数学归纳法的有效性（归谬法）  假设∀n P(n)不成立，则∃n (¬P(n))成立.  令S={ n ∈Ζ| (n≥a)∧¬P(n) }，S是非空子集.  根据良序公理，S有最小元素，记为m, ma  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(k)→P(k+1) （强）数学归纳法（举例）  对每个正整数n ≥4，n! 2n  基础步骤：P(4)为真，24 16  归纳步骤：对任意正整数k ≥4, P(k) ⇒P(k+1). (k+1)!= (k+1) k! (k+1) 2k 2k+1  因此，对任意正整数n ≥4, P(n) 成立. Odd Pie Fights （奇数个馅饼的战斗）  Placing an odd number of people in the plane, in such a way that every