數(shù)序歸納法——如何征服無(wú)窮序列
高斯求和
- 思考題——存錢罐里的錢
- 第1天榔昔，往存錢罐里投入1元蜈项，存錢罐總金額為1元
- 第2天，往存錢罐里投入2元晨雳，存錢罐總金額為3元
- 第3天行瑞，往存錢罐里投入3元，存錢罐總金額為6元
- 第4天餐禁，往存錢罐里投入4元血久，存錢罐總金額為10元
每天如此存錢，問(wèn)100天時(shí)坠宴，是多少存款洋魂？
- 高斯求和的思路
當(dāng)然就是1+100，2+99, 3+98, ... 100+1喜鼓，共有50個(gè)101
101 * 50 = 5050
討論一下高斯的方法副砍，高斯求和的本質(zhì)可以運(yùn)用到很多場(chǎng)景，TA的本質(zhì)是把累加器的算法庄岖，簡(jiǎn)化到只有三步即可完成：
比如1加到1億豁翎，只需要一次加法和一次乘法，一次除法即可完成：((100000000+1) * 100000000) / 2
歸納
- 0以上的整數(shù)斷言
- 斷言A(n): n * 2 是偶數(shù)
- 斷言B(n): n * 3 是奇數(shù)
- 可以用以下有關(guān)n的斷言形式來(lái)表現(xiàn)高斯的觀點(diǎn)
斷言G(n): 0到n的整數(shù)之和為 n*(n+1)/2
但是如何證明0以上無(wú)窮多個(gè)整數(shù)都正確呢隅忿？必須引入“數(shù)學(xué)歸納法”
數(shù)學(xué)歸納法 是證明有關(guān)整數(shù)的斷言對(duì)于0以上的所有整數(shù)n都成立
時(shí)所使用的方法
主要經(jīng)過(guò)兩個(gè)步驟進(jìn)行證明：
- 證明P(0)成立
- 證明不論k為0以上的哪個(gè)整數(shù)心剥，若P(k)成立，則P(k+1)也成立
第一步背桐，我們稱作基底(base)优烧；第二步，稱作歸納(induction)链峭。
黑白棋思考題——錯(cuò)誤的數(shù)學(xué)歸納法
- 斷言T(n)：投擲n枚黑白棋畦娄，所有棋子的顏色一定相同。
- 基底的證明： T(1)，當(dāng)棋子只有1個(gè)的時(shí)候熙卡，T(1)成立杖刷。
- 除去1和k，k-1中共有兩色棋子驳癌，不能成立k-1=0滑燃，所以不存在同屬于兩個(gè)組的棋子。
因此颓鲜，步驟二是無(wú)法得到證明的表窘。
