最近在学习《算法导论》时，发现很多证明都用到了数学归纳法，这里查了点资料，把数学归纳法复习一下：
数学归纳法用来在数学上证明与自然数N有关的命题的一种特殊方法，它主要用来研究与正整数有关的数学问题，在高中数学中常用来证明等式成立和数列通项公式成立。
用的最多的是第一数学归纳法和第二数学归纳法，下面详细说明。
第一数学归纳法
- 证明当n（n为自然数）取第一个值时命题成立
- 假设当n=k（k为自然数）时命题成立，证明当n=k+1时命题也成立
由1，2步，可证明命题成立。
第二数学归纳法
对第一数学归纳法进行了扩充
- 证明当n=0时命题成立
- 假设当n<=k（k为自然数）时命题成立，证明当n=k+1时命题也成立
有1，2步，可证明命题成立。
在算法时间复杂度的证明上，由于n取值是一个自然数，所以多用数学归纳法原理进行证明。其实，证明循环正确性的循环不变式就是直接利用的第一数学归纳法。
参考：
百度百科，数学归纳法
文章来源:
http://localhost/wp2/?p=165