數學歸納法的證明與應用

傲月光希

在數學的領域裡，最基本的就是數字了，有了數字的發明，使得在數學這塊領域能夠發展到至今的程度。數字最先是有正整數，也就是自然數，因為這是在人類出現之前就存在的，是上天的創造。之後人類陸續創造出0跟負整數，甚至分數、無理數跟小數，因而創造出了整個實數系。

而今天這篇文章，我們所要談的是整數的奧妙，整數也是有它的理論存在，因此就出現了「數論」(Numeral Theory)。接下來我們將慢慢地進入這塊領域中。

第一個我們要說的就是「良序原理」(Well-Ordering Principle)。良序原理講到的就是正整數系中的每個元素都有排列的關係，也就是大小關係，這邊需要一點集合的概念。
它的敘述是這樣的－對於任一個非空飛負整數的集合S且包含一個最小的元素，對所有S中的元素b必存在某個元素a使得a≦b。

利用良序原理，我們可以證明之後的阿基米德性質跟數學歸納法。


定理一：阿基米德性質(Archimedean Property)
敘述：若a跟b是任意兩正整數，則存在一正整數n使得na≧b。
證明：
我們要用到反證法，所謂的反正法就是先假設結論錯誤，經由正確的推導會得到矛盾的結果。假設有特定一組a跟b會使得na<b，則設一個集合S={b-na | n是任意正整數}，且S為非空。因為S中的元素皆為正整數，由梁序原理知道存在一個最小的元素，假定為b-ma。b-(m+1)a也在S中，因此b-(m+1)a=(b-ma)-a<b-ma為更小的元素，這與前面假設的矛盾，因此原結論為真。

阿基米德性質告訴我們任兩個正整數，其中一個一定能夠堆疊到大於等於另一個正整數。

接著，我們要來證明數學歸納法。數學歸納法在很多數學的證明當中是蠻實用的，通常只要一個定理或理論牽涉到正整數時，我們幾乎都可以用數學歸納法來證明。數學歸納法基本上分成兩種，第一數學歸納法與第二數學歸納法，而兩者之間只有些許的差異，這個在之後的證明中會提到。


定理二：第一數學歸納法(The First Principle of Mathematical Induction)
敘述：
令S是一個包含正整數的集合且滿足下列兩性質：
(1)正整數1在S中
(2)若一正整數k屬於S，則k+1必屬於S
則S是包含所有正整數的集合。
證明：
這邊我們要用到反證法。假設S是滿足條件但不包含所有的正整數，令T為包含不在S中的正整數的集合，則由良序原理得知T有最小的正整數，假設為k。因為k-1比k更小，所以k-1包含在S中。又1屬於S，因此由第二個條件知道(k-1)+1=k屬於S，矛盾。因此原結論為真。

接著，我們來用數學歸納法來證明一個簡單的例子。


例一：請證明(1^2)+(2^2)+...+(n^2)=n(n+1)(2n+1)/6，對所有正整數n。
證明：
(1)n=1，1^2=[1*(1+1)(2*1+1)]/6，成立。
(2)假設當n=k時成立，則n=k+1時，(1^2)+(2^2)+...+(k^2)+[(k+1)^2]=k(k+1)(2k+1)/6+[(k+1)^2]=(k+1)[k(2k+1)/6+(k+1)]=(k+1)(2k^2+k+6k+6)/6=(k+1)(2k^2+7k+6)/6=
(k+1)(k+2)(2k+3)/6=(k+1)[(k+1)+1][2(k+1)+1]/6，成立。
由(1)、(2)跟數學歸納法，原敘述成立。

接下來，我們要介紹第二數學歸納法。而第二與第一的差別是在於第二個條件，第一是只針對一個k成立，k+1就成立，而第二是針對所有小於等於k的正整數都成立時，k+1也會成立。


定理三：第二數學歸納法(The Second Principle of Mathematical Induction)
敘述：
對於一正整數集合S滿足下列兩個性質：
(1)正整數1在S中
(2)對於所有小於等於k的情況都屬於S，則k+1也屬於S
則S是包含所有正整數的集合。
證明：由於與第一數歸法證法相似，因此留給大家自己去證明看看。

這邊來舉個可以利用第二數歸法證明的例子。


例二：有一種數列稱為Lucas數列，可表示成遞迴數列如下：
a_1=1
a_2=3
a_n=a_(n-1)+a(n-2)，對所有正整數n≧3
則請證明a_n<(7/4)^n。

證明：
(1)n=1，a_1=1<(7/4)^1，成立。
(2)假設對於所有小於等於k的正整數都成立，則當n=k+1時，a_(k+1)=a_k+a_(k-1)<(7/4)^k+(7/4)^(k-1)=[(7/4)^(k-1)](7/4+1)=[(7/4)^(k-1)](11/4)<[(7/4)^(k-1)][(7/4)^2]=
(7/4)^(k+1)，成立。
由(1)、(2)及第二數學歸納法得知，原敘述成立。

[ 本文最後由 傲月光希 於 07-9-5 11:40 AM 編輯 ]