powerpointpresentation-南京大學(xué)

1、數(shù)學(xué)歸納法,離散數(shù)學(xué)─歸納與遞歸南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系,內(nèi)容提要,數(shù)學(xué)歸納法強(qiáng)數(shù)學(xué)歸納法運(yùn)用良序公理來(lái)證明,數(shù)學(xué)歸納法,,數(shù)學(xué)歸納法（有效性）,良序公理正整數(shù)集合的非空子集都有一個(gè)最小元素?cái)?shù)學(xué)歸納法的有效性（歸謬法）假設(shè)?n P(n)不成立，則 ?n (?P(n))成立.令S={ n??+ | ?P(n)}，S是非空子集.根據(jù)良序公理，S有最小元素，記為m, m?1(m-1)?S, 即P(m-1)成立. 根據(jù)歸

2、納步驟，P(m)成立，即m?S，矛盾.因此，?n P(n)成立.,數(shù)學(xué)歸納法（舉例）,Hk=1+1/2+…+1/k （k為正整數(shù)）證明：H2n ?1+n/2 （n為正整數(shù)）基礎(chǔ)步驟：P(1)為真， H2=1+1/2歸納步驟：對(duì)任意正整數(shù)k, P(k) ?P(k+1). H2k+1 = H2k +1/(2k+1)+…+1/2k+1 ?(1+k/2)+2k(1/2k+1) =1+(1+

3、k)/2 因此，對(duì)任意正整數(shù)n, P(n) 成立.,數(shù)學(xué)歸納法（舉例）,猜測(cè)前n個(gè)奇數(shù)的求和公式，并證明之。1=11+3=41+3+5=91+3+5+7=16…1+3+…+(2n-1)=n2（n為正整數(shù)）運(yùn)用數(shù)學(xué)歸納法證明（練習(xí)）,運(yùn)用數(shù)學(xué)歸納法時(shí)犯的錯(cuò)誤,,強(qiáng)數(shù)學(xué)歸納法,,強(qiáng)數(shù)學(xué)歸納法（一般形式）,設(shè)P(n)是與整數(shù)n有關(guān)的陳述， a和b是兩個(gè)給定的整數(shù)，且a ? b.

4、 如果能夠證明下列陳述P(a), P(a +1), …, P(b).對(duì)任意k ? b, P(a)?… ?P(k)?P(k+1)則下列陳述成立對(duì)任意n ? a, P(n).,強(qiáng)數(shù)學(xué)歸納法（有效性）,{ n?Z | n ? a }是良序的良序集：該集合的非空子集都有一個(gè)最小元素強(qiáng)數(shù)學(xué)歸納法的有效性（歸謬法）假設(shè)?n P(n)不成立，則 ?n (?P(n))成立.令S={ n?? | (n?a)? ?P(n) }，S是非空子

5、集.根據(jù)良序公理，S有最小元素，記為m, m>ba, …, (m-1)?S, 即P(a), …, P(m-1)成立, 其中 m-1 ? b. 根據(jù)歸納步驟，P(m)成立，即m?S，矛盾.因此，?n P(n)成立.,強(qiáng)數(shù)學(xué)歸納法（舉例）,任意整數(shù)n(n ?2)可分解為（若干個(gè)）素?cái)?shù)的乘積n = 2.考察 n+1.用4分和5分就可以組成12分及以上的每種郵資.P(12), P(13), P(14), P(15).對(duì)任

6、意k ?15, P(12)?… ?P(k)?P(k+1),（強(qiáng)）數(shù)學(xué)歸納法（舉例）,對(duì)每個(gè)正整數(shù)n ? 4，n! ? 2n基礎(chǔ)步驟：P(4)為真，24 ?16歸納步驟：對(duì)任意正整數(shù)k ?4, P(k) ? P(k+1). (k+1)!= (k+1) k! ? (k+1) 2k ? 2k+1 因此，對(duì)任意正整數(shù)n ? 4, P(n) 成立.,運(yùn)用良序公理來(lái)證明（舉例）,設(shè)a是整數(shù), d是正整數(shù), 則存在唯一的整數(shù)q和

7、r滿足0 ? r < d a =dq+ r證明令S={a-dq | 0?a-dq ，q?Z}，S非空.非負(fù)整數(shù)集合具有良序性S有最小元，記為r0 = a-dq0.可證 0 ? r0 < d 唯一性證明， 0 ? r1 - r0 = d (q0-q1) ? d，因此，q1=q0,運(yùn)用良序公理來(lái)證明（舉例）,在循環(huán)賽勝果圖中，若存在長(zhǎng)度為m（m?3）的回路，則必定存在長(zhǎng)度為3的回路。 備注： ai ?

8、 aj 表示ai贏了aj證明設(shè)最短回路的長(zhǎng)度為k //良序公理的保證 假設(shè) k?3 a1 ? a2 ? a3 ?… ? ak? a1 若a3? a1, 存在長(zhǎng)度為3的回路，矛盾。若a1 ? a3, 存在長(zhǎng)度為(k-1)的回路，矛盾。,Odd Pie Fights （奇數(shù)個(gè)餡餅的對(duì)抗）,Placing an odd number of people in the plane, in such a way that every

9、pair of people has a distinct distance between them. At a signal, each person will throw a pie at the closest other person. At least one person does not get hit with a pie？,作業(yè),教材[4.1, 4.2]P209-214：18, 20, 63P220-223：7