第二数学归纳法
数学归纳法分为第一数学归纳法和第二数学归纳法
一般我们都是使用第一数学归纳法，但是对于第二数学归纳法，在算法导论中也是经常使用，比如22.4-2中证明算法正确性时会用到。
第二数学归纳法原理是设有一个与自然数n有关的命题，如果：
（1）当n＝1时，命题成立；
（2）假设当n≤k时命题成立，由此可推得当n＝k+1时，命题也成立。
那么，命题对于一切自然数n来说都成立。
还有二元数学归纳法：
在Young表的算法正确性证明中会用到。
当m=1，对于任意的n，成立。
假设m=k，对于任意的n，成立。
当m=k+1时，
(1)n=1时，成立。
(2)假设n=j时，成立。
(3)当n=j+1时，成立。
版权声明：本文为xiazdong原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。