數學歸納法
| 數學歸納法 |
數學歸納法（Mathematical Induction, MI）是一種數學證明方法，通常被用於證明某個給定命題在整個（或者局部）自然數範圍內成立。除了自然數以外，廣義上的數學歸納法也可以用於證明一般良基結構，例如：集合論中的樹。這種廣義的數學歸納法應用於數學邏輯和計算機科學領域，稱作結構歸納法。
目錄
簡介
數學歸納法（Mathematical Induction, MI）是一種數學證明方法，通常被用於證明某個給定命題在整個（或者局部）自然數範圍內成立。除了自然數以外，廣義上的數學歸納法也可以用於證明一般良基結構，例如：集合論中的樹。這種廣義的數學歸納法應用於數學邏輯和計算機科學領域，稱作結構歸納法。在數論中，數學歸納法是以一種不同的方式來證明任意一個給定的情形都是正確的（第一個,第二個，第三個，一直下去概不例外）的數學定理。雖然數學歸納法名字中有「歸納」，但是數學歸納法並非不嚴謹的歸納推理法，它屬於完全嚴謹的演繹推理法。事實上，所有數學證明都是演繹法。
評價
數學歸納法的原理，通常被規定作為自然數公理（參見皮亞諾公理）。但是在另一些公理的基礎上，它可以用一些邏輯方法證明。數學歸納法原理可以由下面的良序性質（最小自然數原理）公理可以推出：自然數集是良序的。（每個非空的正整數集合都有一個最小的元素）比如{1, 2, 3 , 4, 5}這個正整數集合中有最小的數——1.下面我們將通過這個性質來證明數學歸納法：對於一個已經完成上述兩步證明的數學命題，我們假設它並不是對於所有的正整數都成立。對於那些不成立的數所構成的集合S，其中必定有一個最小的元素k。（1是不屬於集合S的，所以k>1）k已經是集合S中的最小元素了，所以k-1是不屬於S，這意味着k-1對於命題而言是成立的——既然對於k-1成立，那麼也對k也應該成立，這與我們完成的第二步驟矛盾。所以這個完成兩個步驟的命題能夠對所有n都成立。注意到有些其它的公理確實是數學歸納法原理的可選的公理化形式。更確切地說，兩者是等價的。已知最早的使用數學歸納法的證明出現於Francesco Maurolico的Arithmeticorum libri duo（1575年）。Maurolico利用遞推關係巧妙地證明出前n個奇數的總和是n^2，由此總結出了數學歸納法。最簡單和常見的數學歸納法證明方法是證明當n屬於所有正整數時一個表達式成立，這種方法是由下面兩步組成：遞推的基礎：證明當n=1時表達式成立。遞推的依據：證明如果當n=m時成立，那麼當n=m+1時同樣成立。這種方法的原理在於第一步證明起始值在表達式中是成立的，然後證明一個值到下一個值的證明過程是有效的。如果這兩步都被證明了，那麼任何一個值的證明都可以被包含在重複不斷進行的過程中。[1]