数序归纳法——如何征服无穷序列
高斯求和
- 思考题——存钱罐里的钱
- 第1天，往存钱罐里投入1元，存钱罐总金额为1元
- 第2天，往存钱罐里投入2元，存钱罐总金额为3元
- 第3天，往存钱罐里投入3元，存钱罐总金额为6元
- 第4天，往存钱罐里投入4元，存钱罐总金额为10元
每天如此存钱，问100天时，是多少存款？
- 高斯求和的思路
当然就是1+100，2+99, 3+98, ... 100+1，共有50个101
101 * 50 = 5050
讨论一下高斯的方法，高斯求和的本质可以运用到很多场景，TA的本质是把累加器的算法，简化到只有三步即可完成：
比如1加到1亿，只需要一次加法和一次乘法，一次除法即可完成：((100000000+1) * 100000000) / 2
归纳
- 0以上的整数断言
- 断言A(n): n * 2 是偶数
- 断言B(n): n * 3 是奇数
- 可以用以下有关n的断言形式来表现高斯的观点
断言G(n): 0到n的整数之和为 n*(n+1)/2
但是如何证明0以上无穷多个整数都正确呢？必须引入“数学归纳法”
数学归纳法 是证明有关整数的断言对于0以上的所有整数n都成立
时所使用的方法
主要经过两个步骤进行证明：
- 证明P(0)成立
- 证明不论k为0以上的哪个整数，若P(k)成立，则P(k+1)也成立
第一步，我们称作基底(base)；第二步，称作归纳(induction)。
黑白棋思考题——错误的数学归纳法
- 断言T(n)：投掷n枚黑白棋，所有棋子的颜色一定相同。
- 基底的证明： T(1)，当棋子只有1个的时候，T(1)成立。
- 除去1和k，k-1中共有两色棋子，不能成立k-1=0，所以不存在同属于两个组的棋子。
因此，步骤二是无法得到证明的。
