最近在學(xué)習(xí)《算法導(dǎo)論》時(shí)，發(fā)現(xiàn)很多證明都用到了數(shù)學(xué)歸納法，這里查了點(diǎn)資料，把數(shù)學(xué)歸納法復(fù)習(xí)一下：

數(shù)學(xué)歸納法用來(lái)在數(shù)學(xué)上證明與自然數(shù)N有關(guān)的命題的一種特殊方法，它主要用來(lái)研究與正整數(shù)有關(guān)的數(shù)學(xué)問(wèn)題，在高中數(shù)學(xué)中常用來(lái)證明等式成立和數(shù)列通項(xiàng)公式成立。

用的最多的是第一數(shù)學(xué)歸納法和第二數(shù)學(xué)歸納法，下面詳細(xì)說(shuō)明。

第一數(shù)學(xué)歸納法

1. 證明當(dāng)n（n為自然數(shù)）取第一個(gè)值時(shí)命題成立
2. 假設(shè)當(dāng)n=k（k為自然數(shù)）時(shí)命題成立，證明當(dāng)n=k+1時(shí)命題也成立

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

第二數(shù)學(xué)歸納法

對(duì)第一數(shù)學(xué)歸納法進(jìn)行了擴(kuò)充

1. 證明當(dāng)n=0時(shí)命題成立
2. 假設(shè)當(dāng)n<=k（k為自然數(shù)）時(shí)命題成立，證明當(dāng)n=k+1時(shí)命題也成立

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

在算法時(shí)間復(fù)雜度的證明上，由于n取值是一個(gè)自然數(shù)，所以多用數(shù)學(xué)歸納法原理進(jìn)行證明。其實(shí)，證明循環(huán)正確性的循環(huán)不變式就是直接利用的第一數(shù)學(xué)歸納法。

參考：

百度百科，數(shù)學(xué)歸納法