数学归纳法的证明
维基百科，自由的百科全书
[编辑] 证明
一个简化的证明方法在下面给出。这个证明为了能让那些没有经过太多数学训练的读者也能够读懂，没有用到“存在(there exists)”和“对所有元素而言(all)”的数学符号。这个证明的关键思路是自然数减法和反证法。
假设：
- (1) P(0)
和
- (2) 对所有的n ≥ 0, P(n) ⇒ P(n + 1)
这两个命题成立。
考虑如下命题：
- (3) 对所有的 m ≥ 0, P(m)成立
就是说对所有m的整数值，P皆为真。
假设此命题为假，即等价于
- (4) 存在能使非P(m)成立的m。
此证明试图证明若(1)，(2)为真，可推出(4)为假，从而得出命题(3)成立。
假设(1)，(2)，(4)命题成立。
由命题(4)，令m′为能使非P(m′)成立的最小值。
显然，m′不能为0，因为这样做会立即导致一个矛盾：(P(0) & 非 P(0)) with P(0) - 与命题(1)矛盾。
假设m′>0
由m′的定义可知，P(m′ - 1)成立，因此由(2)，P(m′)成立。这也有矛盾：P(m′) & 非 P(m′)同时成立。
因此得出，由(1)，(2)命题只能推出非(4)成立，即前面所述的命题(3)成立。
因此，有：
- (1) P(0)
及
- (2) P(n) ⇒ P(n + 1)
成立，可推出（有小小的换元）
- (3) 对于所有的 n ≥ 0, P(n)成立。
这个即为数学归纳法原理。
