證明 數學歸納法

數學歸納法(Mathematical Induction)立論的基礎是來自良序原理(Well-Ordering Property)。
Well-Ordering Property告訴我們：任何自然數的非空子集合會有一個最小的元素。(Every nonempty subset of the set of positive integers has a least element.)

首先我先以矛盾證法證明數學歸納法的合法性(Validity)：

假設已知條件：P(1)為真，且對所有自然數k而言，敘述 P(k)→P(k+1)亦為真。

為證明P(n)對所有自然數n而言恆為真的話，假設存在一自然數n使得P(n)為假。
則根據Well-Ordering Property，讓P(n)為假的自然數集合S是自然數集合N的子集合，它是個非空集合，並存在一個最小的元素，我們稱此元素為m。
我們知道m不會是1，因為已知條件中已給出P(1)為真。
既然m不會是1，那它必定是個大於1的自然數，m-1也會是個自然數。
此外，因為m-1小於m，m已經是S集合中最小的元素了，所以m-1並不屬於S集合；因此知P(m-1)必為真。
所以我們得到了P(m-1)為真，P(m)為假的結論。
根據已知條件：P(k)→P(k+1) (P(k)為真，則P(k+1)亦為真)，我們知道這個結論和已知條件矛盾，因此推得"存在一自然數n使P(n)為假"這個敘述是錯誤的！
也就是說，P(n)對任何自然數n恆為真。得證！


refer from:
http://tw.myblog.yahoo.com/jw!XToZojWTHRI2EfbctdR8ag--/article?mid=1628&prev=1629&l=f&fid=78