《算法引论》笔记

学习阶段

数学归纳法的等价定义

基本条件：

1. 当 $n=1$ 时，$T$ 成立；
2. 对任意 $n>1$，如果 $n-1$ 时 $T$ 成立，那么 $n$ 时 $T$ 也成立

定义：如果对于带有参数 $n$ 的命题 $P$ ，当 $n=1$ 时 $Р$ 成立；并且如果对每一个 $n (n>1)$,若 $n-1$ 时 $P$ 成立能推出 $n$ 时 $Р$ 也成立；那么对任意自然数，$Р$ 都成立。

等价一：如果对于带有参数n的命题P，当n= 1时Р成立;并且如果对每一个n (n ≥ 1 ),若n时Р成立能推出n+1时Р也成立;那么对任意自然数，Р都成立。

等价二：如果对于带有参数n的命题P，当n=1时Р成立;并且如果对每一个n (n> 1 ),若对任意小于n的自然数Р成立能推出对n命题Р也成立;那么对任意自然数,Р都成立。

等价三：如果对于带有参数n的命题P，当n=1和n=2时Р都成立;并且如果对每一个n (n >2)，若n-2时Р成立能推出n时Р也成立;那么对任意自然数，Р都成立。

等价四：如果对于带有参数n的命题P，当n=1和n=2时Р都成立;并且如果对每一个n (n >2)，若n-2时Р成立能推出n时Р也成立;那么对任意自然数，Р都成立。

一些公式

1. $x^n-1$ 能被 $x-1$ 除尽;
2. 前n个自然数和为 n(n+1)/2;
3. 级数 $8+13+18+23+···+(3+5n)$ 之和是 $2.5n^2+5.5n$
4. $(1+x)^n>=1+nx$

证明的思路

1. 证明增长率