最近在學習《算法導論》時，發現很多證明都用到了數學歸納法，這里查了點資料，把數學歸納法復習一下：

數學歸納法用來在數學上證明與自然數N有關的命題的一種特殊方法，它主要用來研究與正整數有關的數學問題，在高中數學中常用來證明等式成立和數列通項公式成立。

用的最多的是第一數學歸納法和第二數學歸納法，下面詳細說明。

第一數學歸納法

1. 證明當n（n為自然數）取第一個值時命題成立
2. 假設當n=k（k為自然數）時命題成立，證明當n=k+1時命題也成立

由1，2步，可證明命題成立。

第二數學歸納法

對第一數學歸納法進行了擴充

1. 證明當n=0時命題成立
2. 假設當n<=k（k為自然數）時命題成立，證明當n=k+1時命題也成立

有1，2步，可證明命題成立。

在算法時間復雜度的證明上，由于n取值是一個自然數，所以多用數學歸納法原理進行證明。其實，證明循環正確性的循環不變式就是直接利用的第一數學歸納法。

參考：

百度百科，數學歸納法