算法导论中用到的数学归纳法

大家好，欢迎来到IT知识分享网。

在学习算法导论的过程中，看见一些证明的时候是一头雾水，不知道为什么是这么证明的，于是去看了mit的算法导论公开课，在课程中我逐渐理解了他所使用的归纳法。

数学归纳法总共有两种。

第一数学归纳法可以概括为以下三步：

(1)归纳奠基：证明n=1时命题成立；

(2)归纳假设：假设n=k时命题成立；

(3)归纳递推：由归纳假设推出n=k+1时命题也成立．

第二数学归纳法原理是设有一个与自然数n有关的命题，如果：

（1）当n＝1时，命题成立；

（2）假设当n<k时命题成立，由此可推得当n＝k时，命题也成立。

那么，命题对于一切自然数n来说都成立。

理解了这两种数学归纳法，再去理解算法导论中的证明部分就不难了。

————————————————2024.7.8修改———————————————————

经过进一步的学习，我发现我之前在学习数学归纳法的时候没有考虑到n=1只是说n取一个开始的边界条件，n可以=1，也可以从2从3开始。