第二數學歸納法

數學歸納法是一種重要的論證方法。我們通常所説的“數學歸納法”大多是指它的第一種形式而言，本文從最小自然數原理出發，對它的第二種形式即第二數學歸納法進行粗略的探討，旨在加深對數學歸納法的認識，並得到一種加強的證明方法。相對於第一數學歸納法，第二數學歸納法的假設更強，理論上可以使用第一數學歸納法證明的，必然可以使用第二數學歸納法證明；反之則不一定成立，我們有一個有關整數的整除理論的典型證明：“所有大於1的整數都可以分解成若干個素數的乘積”來看出這一點。

1.最小自然數原理：

設T是N的一個非空子集，那麼必有t₀屬於T，使得對任意t屬於T，有t₀<=t,即t₀是T中最小自然數。 ^[1] 

2.第二數學歸納法：

設有一個與自然數n有關的命題P₀，P₁，P₂,…,P_n如果： ^[1] 

（1）當n=1，P₁成立； ^[1] 

（2）對n>1,若對所有自然數m<n,P_m成立，推出P_n成立； ^[1] 

命題對於一切自然數n來説都成立。 ^[1] 

證明：假設命題不是對一切自然數都成立

設C表示使命題不成立的自然數所組成的集合，C非空 ^[1] 

由最小自然數原理可得，C中必然存在最小元素t₀ ^[1] 

由(1) P₁成立，知t₀>1 ^[1] 

由（2）知，取n=t₀有m<t₀,使得P_m不成立 ^[1] 

由C的定義知m屬於C，與t0最小矛盾 ^[1] 

得證

在假如論證在n=k+1時的真偽時，必須以n取不大於k的兩個或兩個以上乃至全部的自然數時命題的真偽為其論證的依據，則一般選用第二數學歸納法進行論證。之所以這樣，其根本原則在於第二數學歸納法的歸納假設的要求較之第一數學歸納法更強，不僅要求命題在n=k時成立，而且還要求命題對於一切小於k的自然數來説都成立，反過來，能用第一數學歸納法來論證的數學命題，一定也能用第二數學歸納進行證明，這一點是不難理解的。不過一般説來，沒有必要這樣做。

第二數學歸納法和第一數學歸納法一樣，也是數學歸納法的一種表達形式，而且可以證明第二數學歸納法和第一數學歸納法是等價的，之所以採用不同的表達形式，旨在更便於我們應用。