數學歸納法證明的原理

時間：2024-05-12 04:20:00

數學歸納法證明的原理

數學歸納法證明的原理

數學歸納法證明的原理

　　數學歸納法證明的是與自然數有關的命題，它的依據是皮亞諾提出的自

　　然數的序數理論，就是通常所說的自然數的皮亞諾公理，內容是：

　　（１）ｌ是自然數。

　　（２）每個自然數ａ有一個確定的“直接后繼”數ａ’，ａ也是自然數。

　　（２）ａ’≠１，即１不是任何自然數的“直接后繼”數。

　　（４）由ａ’＝ｂ’，推得ａ＝ｂ，即每個自然數只能是另外的唯一自然的“直

　　接后繼”數。

　　（５）任一自然數的集合，如果包含１，并且假設包含ａ，也一定包含ａ

　　的“直接后繼”數ａ’，則這個集合包含所有的自然數。

　　皮亞諾公理中的（５）是數學歸納法的依據，又叫歸納公理

　　數學歸納法的應用及舉例。

　　因為由假設知４２ｋ＋１＋３ｋ＋２能被１３整除，１３４２ｋ＋１也能被１３整除，這就

　　是說，當ｎ＝ｋ＋１時，ｆ（ｋ＋ｌ）能被１３整除。根據（１）、（２），可知命題

　　對任何ｎ∈Ｎ都成立。

　　下面按歸納步中歸納假設的形式向讀者介紹數學歸納法的幾種不同形式

　　以及它們的應用。

　　（ｌ）簡單歸納法。即在歸納步中，歸納假設為“ｎ＝ｋ時待證命題成立”。

　　這是最常用的一種歸納法，稱為簡單歸納法，大家都比較熟悉，這里不再贅

　　述。

　　（２）強歸納法。這種數學歸納法，在歸納步中，其歸納假設為“ｎ≥ｋ

　　時待證命題成立”。我們稱之為強歸納法，又叫串值歸納法。

　　通常，如果在證明ｐ（ｎ＋ｌ）成立時，不僅依賴于ｐ（ｎ）成立，而且還

　　可能依賴于以前各步時，一般應選用強歸納法，下面舉例說明其應用。

　　例有數目相等的兩堆棋子，兩人輪流從任一堆里取幾項棋子，但不能

　　不取也不能同時從兩堆里取，規定凡取得最后一項者勝。求證后者必勝。

　　證：歸納元ｎ為每堆棋子的數目。設甲為先取者，乙為后取者。

　　奠基ｎ＝ｌ，易證乙必勝。

　　歸納設Ｎｎ≤ｋ時，乙必勝。現證ｎ＝ｋ＋ｌ時也是乙必勝。

　　設甲在某堆中先取ｒ顆，Ｏ＜ｒ≤ｋ。乙的對策是在另一堆中也取ｒ顆。有

　　二種可能：

　　（１）若ｒ＜ｋ，經過兩人各取一次之后，兩堆都只有ｋ－ｒ顆，ｋ－ｒ＜ｋ，

　　現在又輪到甲先取，依歸納假設，乙必勝。

　　（２）若ｒ＝ｋ，顯然是乙勝，證畢。

　　上述形式的歸納法雖然比較簡單，但如使用不當，往往會發生錯誤，有

　　兩點應注意：第一，在使用歸納假設時防止無形中引入不相干的假設。第二，

　　在證明過程中應注意數學規律的正確性。下面我們引入一個反例，在這個反

　　例中，由于錯誤的證明導致證得了錯誤的待證命題。

　　反倒：證明任意ｎ條直線均能重合成一條直線。

　　下面給出錯誤的證明：

　　證：奠基ｎ＝１時該命題成立。

　　歸納利用強歸納法，可以有如下的歸納假設：任意１條，２條，３條，…，

　　ｋ條直線均重合成一條直線，要證ｋ＋１條直線也重合成一條直線，設這ｋ＋１

　　條直線為ｌ１、ｌ２、…，ｌｋ，ｌｋ＋１由強歸納假設得ｌ１，…，ｌｋ…重合為一條直線，

　　記為ｌ。又由強歸納假設得ｌ和ｌｋ＋１重合為一條直線，于是任意ｎ條直線便

　　重合一條直線了。

　　細心的讀者也許已經發現這里的錯誤了，這是由于錯誤地使用了強歸納

　　假設而造成的。具體地說，這是在“ｌ和ｌｋ＋１這兩條直線重合為一條直線”

　　這一點把強歸納假設使用錯了。強歸納假設中并沒有包含這一條件，因為我

　　們這里奠的基是ｎ＝ｌ，因此待證命題“ｋ＋１條直線重合為一條直線”要求對于

　　一切大于等于１的ｋ成立，而上面證明中所假設的ｌ和ｌｋ＋１重合為一條直線

　　實際上是要求ｋ≥２，這就是錯誤的所在。

　　（３）參變歸納法。在待證命題中含有參數的時候，例如Ｐ（ｕ，ｎ），則

　　用數學歸納法證明Ｐ（ｕ，ｎ）對一切ｎ成立時，在奠基步中，應證Ｐ（ｕ，０）

　　對一切ｕ成立。在歸納步中，假設Ｐ（ｕ，ｋ）對一切ｕ成立，證明Ｐ（ｕ，ｋ＋１）

　　對一切ｕ成立。這里，“Ｐ（ｕ，ｋ）”對一切ｕ成立稱之為參變歸納假設，這

　　種證明方法叫做參變歸納法，Ｕ起著參數的作用。

　　例求證當ｎ≥３時有ｎ（ｎ＋１）≥（ｎ＋１）３。

　　本題證明的困難主要在于歸納步驟，無論采用哪種歸納假設，都難于證

　　明。如果我們對該待證命題施展一定的技巧，把該式中的部分ｎ寫成ｕ（視

　　作參數），部分ｎ保持不變，即寫成

　　ｎｕｎ≥（ｕ＋ｌ）ｎ，

　　則可用參變歸納法證明當ｕ≥ｎ≥３時上式成立，原命題即可得證。

　　奠基ｎ＝３時，對ｕ≥３的一切ｕ均有

　　右端＝３ｕ３＝ｕ３＋ｕｕ２ｕ

　　≥ｕ３＋３ｕ＋ｇｕ

　　＞ｕ３＋３ｕ２＋３ｕ＋１

　　＝（ｕ＋１）３＝右端

　　歸納ｎ＝ｋ＋１時，

　　左端＝（ｋ＋１）Ｕｋ＋１＝ｕ（ｋ＋１）ｕｋ

　　＝（ｕｋ十ｕ）ｕｋ≥（ｕｋ十ｋ）Ｕｋ

　　＝ｋ（ｕ＋ｌ）ｕｋ≥（ｎ＋１）（ｕ＋１）ｋ

　　＝（Ｕ＋ｌ）ｋ＋１＝右端。

　　所以當ｕ≥ｎ≥３時，有ｎｕｎ＞（ｕ＋ｌ）ｎ。

　　令ｕ＝ｎ，上式便為ｎｎ＋１≥（ｎ＋ｌ）ｎ，即為原不等式，故原不等式得證。

　　值得指出的是，上面三種形式的數學歸納法，都要求待證命題含有自然

　　數變元ｎ，對ｎ施行歸納，ｎ稱為歸納變元，但是在數學的一些分支中，有些

　　待證命題表面上看來似乎不含自然數變元ｎ，但仔細一分析，實際上是含有

　　自然數變元的，當我們一旦把ｎ的含義明確以后，用數學歸納法去證明這些

　　待證命題就迎刃而解了。舉一個簡單的例子。

　　例證明由｛ａ，ｂ，ｃ，ｄ｝四個標識符利用＋、－運算符組成的任意算術

　　表達式中，所含標識符的個數一定等于這個表達式中運算符的個數加１。

　　證：設任意的表達式為ｆ，而歸納變元ｎ為ｆ中所含運算符的個數。

　　奠基ｎ＝０，則ｆ由一個標識符組成（因為沒有運算符），所以命題成立。

　　歸納假設ｎ≤ｋ時本命題成立，現證ｎ＝ｋ＋１時本命題也成立。ｆ一

　　定是下述兩種情況之一：

　　ｆ是ｆ１＋ｆ２或ｆ是ｆ１－ｆ２。

　　其中ｆ１，ｆ２所含的運算符個數都小于ｋ＋ｌ，對ｆ１，ｆ２使用歸納假設，可

　　得ｆ１＋ｆ２，ｆ１－ｆ２中所含標識符個數也比各自所含的運算符的個數多１。

　　（４）廣義歸納法。數學歸納法不僅可用于含有自然數變元ｎ的命題，經

　　推廣后，還可用于含有某些其它集合上的命題。這種集合，稱為歸納集。對

　　于一個含有某個歸納集上的變元ｘ的待證命題Ｐ（ｘ），所用的歸納法稱之為

　　廣義歸納法。

　　定義：設有一個集合Ａ，如果它滿足下面三個性質：

　　（１）ａ１，ａ２…，ａｎ是Ａ中的元素（ｎ≥１）；

　　（２）如果ｘ是Ａ中元素，則ｆ１１（ｘ），ｆ１２（ｘ），…ｆ１ｎ１（ｘ）也是Ａ中

　　的元素（ｎ、＞０）；

　　如果ｘ，ｙ是Ａ是元素，則ｆ２１（ｘ、ｙ），ｆ２２（ｘ，ｙ），…ｆ２ｎ２（ｘ，ｙ）

　　也是Ａ中元素（ｎ２＞０）；…；

　　如果ｘ１…，ｘｍ是Ａ中元素，則ｆｍ１ｘｌ…ｘｍ），ｆｍ２（ｘｌ…，ｘｍ），…ｆｍｎｍ

　　（ｘ１…，ｘｍ）也是Ａ中元素（ｍ≥ｌ，ｎｍ＞０）。

　　（３）Ａ中的元素僅限于此。

　　則Ａ稱之為歸納集ａ１，ａ２，…ａｎ稱為該集的開始元素，諸ｆｉｊ稱為該集

　　的生成函數（其中第一下標為該函數的元素，第二下標以區分具有同樣元素

　　的各函數）。

　　按照上述的定義，自然數集是歸納集，它的開始元素是０，生成函數是ｆ

　　（ｘ）＝ｘ＋１。

　　前例中集｛ａ，ｂ，ｃ，ｄ｝的元素利用“＋”，“－”運算所構成的一切表

　　達式的集合是歸納集，開始元素是是ａ，ｂ，ｃ，ｄ，生成函數為ｆ２１（ｘ，ｙ）

　　＝ｘ＋ｙ，ｆ２２（ｘ，ｙ）＝ｘ－ｙ。

　　在證明含有某個歸納集Ａ上的變元Ｘ的待證命題Ｐ（ｘ）時，可用如下的

　　廣義歸納法。

　　奠基步要證明（ａｌ），Ｐ（ａ２），……Ｐ（ａｎ）成立，這里ａｌ，ａ２…，ａｎ

　　是Ａ中的開始元素。

　　歸納法要證明對于１≤ｉ≤ｍ及１≤ｊ≤ｎ的所有ｉ、ｊ對于Ａ中的任何元

　　素ｘ１，ｘ２…，ｘｉ，如果Ｐ（ｘｌ），Ｐ（ｘ２），…，Ｐ（ｘ１）成立，則Ｐ（ｆｉｊ（ｘｘ１，…，

　　ｘｉ））也成立。在例４中，因為表達式所組成的集合是歸納集（記為Ａ），

　　我們可用廣義歸納法證之。

　　奠基：對于Ａ中的四個開始元素ａ，ｂ，Ｃ，ｄ，因為它們的標識符個數為

　　１，而運算符個數均為０，所以命題成立。

　　歸納：對于Ａ中的元素ｘ，ｙ，ｆ２１（ｘ，ｙ）＝ｘ＋ｙ中，我們設ｘ＋ｙ標識

　　符個數為ｍ，運算符個數為ｎ；

　　ｘ中標識符個數為ｍｌ，運算符個數為ｎｌ；

　　ｘ中標識符個數為ｍ２，運算符個數為ｎ２；

　　則

　　ｍ＝ｍｌ＋ｍ２＝（ｎ１＋１）＋（ｎ２＋１）

　　（ｎｌ＋ｎ＋１）＋１＝ｎ＋１．

　　同理可證ｆ２２（ｘ，ｙ）＝ｘ－ｙ也有如上的結果，故依廣義歸納法，本命題

　　成立。

【數學歸納法證明的原理】相關文章：

關于血糖檢測的原理總結03-09

計算機的組成原理教案（精選16篇）10-22

釋放證明04-06

下載文檔到電腦，查找使用更方便

立即下載