数学归纳法

第一数学归纳法： 
 一般地，证明一个与自然数n有关的命题P(n)，有如下步骤： 
 （1）证明当n取第一个值n0时命题成立。n0对于一般数列取值为0或1，但也有特殊情况； 
 （2）假设当n=k（k≥n0，k为自然数）时命题成立，证明当n=k+1时命题也成立。 
 综合（1）（2），对一切自然数n（≥n0），命题P(n)都成立。 
证明： 
假设对于对于命题P(n)满足第一数学归纳法的条件，即当n取第一个值n0时命题成立。当n=k（k≥n0，k为自然数）时命题成立，当n=k+1时命题也成立。 
此时假设P(n)并不对所有自然数都成立。 
那么必定有存在一个使得P(n)不成立的最小的自然数，假设是i。既然i是使得P(n)不成立的最小自然数，则i-1必定能使P(n)成立。 
因此得出P(i-1)成立而P(i)不成立，与此条件——当n=k（k≥n0，k为自然数）时命题成立，当n=k+1时命题也成立相矛盾。 
因此该假设P(n)并不对所有自然数都成立不正确。 
反正法成立。

第二数学归纳法原理是设有一个与自然数n有关的命题，如果： 
 （1）当n＝1时，命题成立； 
 （2）假设当n≤k时命题成立，由此可推得当n＝k+1时，命题也成立。 
 那么，命题对于一切自然数n来说都成立。 
证明： 
假设命题不是对一切自然数都成立。命N表示使命题不成立的自然数所成的集合，显然N非空，于是，由最小数原理N中必有最小数m，那么m≠1，否则将与（1）矛盾。所以m－1是一个自然数。但m是N中的最小数，所以m－1能使命题成立。这就是说，命题对于一切≤m－1自然数都成立，根据（2）可知，m也能使命题成立，这与m是使命题不成立的自然数集N中的最小数矛盾。因此定理获证。