第一数学归纳法

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

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

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

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

从而就可断定命题对于从所有正整数都成立。

数学归纳法的正确性证明：

假设我们已经完成下面的推理

归纳基础：P(0)真；

归纳推理：对于任意k (P(k)→P(k+1))

但是还并非所有自然数都有性质P。

将这些不满足性质P的自然数构成一个非空自然数子集，这样，子集中必定有一个最小的自然数，设为m。

显然m>0，记做n+1，这样n一定具有性质P，即P(n)为真

存在n(P(n)∧¬P(n+1))╞╡对于任意的k(¬P(k)∨P(k+1))不满足╞╡对于任意的k(P(k)→P(k+1))不满足

假设推理结果与已经完成的归纳推理矛盾，所以假设错误。

所有自然数都有性质P。