powerpointpresentation-南京大學

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

2、納步驟，P(m)成立，即m?S，矛盾.因此，?n P(n)成立.,數學歸納法（舉例）,Hk=1+1/2+…+1/k （k為正整數）證明：H2n ?1+n/2 （n為正整數）基礎步驟：P(1)為真， H2=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+

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

4、 如果能夠證明下列陳述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是非空子

5、集.根據良序公理，S有最小元素，記為m, m>ba, …, (m-1)?S, 即P(a), …, P(m-1)成立, 其中 m-1 ? b. 根據歸納步驟，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).對任

6、意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) 成立.,運用良序公理來證明（舉例）,設a是整數, d是正整數, 則存在唯一的整數q和

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

8、 aj 表示ai贏了aj證明設最短回路的長度為k //良序公理的保證 假設 k?3 a1 ? a2 ? a3 ?… ? ak? a1 若a3? a1, 存在長度為3的回路，矛盾。若a1 ? a3, 存在長度為(k-1)的回路，矛盾。,Odd Pie Fights （奇數個餡餅的對抗）,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