數(shù)學(xué)歸納法證明的原理

數(shù)學(xué)歸納法證明的原理

　　數(shù)學(xué)歸納法證明的原理

　　數(shù)學(xué)歸納法證明的是與自然數(shù)有關(guān)的命題，它的依據(jù)是皮亞諾提出的自

　　然數(shù)的序數(shù)理論，就是通常所說的自然數(shù)的皮亞諾公理，內(nèi)容是：

　�。ǎ保�ｌ 是自然數(shù)。

　�。ǎ玻┟總�(gè)自然數(shù) ａ 有一個(gè)確定的“直接后繼”數(shù) ａ’，ａ 也是自然數(shù)。

　�。ǎ玻�ａ’≠１，即 １ 不是任何自然數(shù)的“直接后繼”數(shù)。

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

　　接后繼”數(shù)。

　�。ǎ担┤我蛔匀粩�(shù)的集合，如果包含 １，并且假設(shè)包含 ａ，也一定包含 ａ

　　的“直接后繼”數(shù) ａ’，則這個(gè)集合包含所有的自然數(shù)。

　　皮亞諾公理中的（５）是數(shù)學(xué)歸納法的依據(jù)，又叫歸納公理

　　數(shù)學(xué)歸納法的應(yīng)用及舉例。

　　因?yàn)橛杉僭O(shè)知 ４２ｋ＋１＋３ｋ＋２ 能被 １３ 整除，１３４２ｋ＋１ 也能被 １３ 整除，這就

　　是說，當(dāng) ｎ＝ｋ＋１ 時(shí)，ｆ（ｋ＋ｌ）能被 １３ 整除。根據(jù)（１）、（２），可知命題

　　對(duì)任何 ｎ∈Ｎ 都成立。

　　下面按歸納步中歸納假設(shè)的形式向讀者介紹數(shù)學(xué)歸納法的幾種不同形式

　　以及它們的應(yīng)用。

　�。ǎ欤┖�(jiǎn)單歸納法。即在歸納步中，歸納假設(shè)為“ｎ＝ｋ 時(shí)待證命題成立”。

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

　　述。

　�。ǎ玻�強(qiáng)歸納法。這種數(shù)學(xué)歸納法，在歸納步中，其歸納假設(shè)為“ｎ≥ｋ

　　時(shí)待證命題成立”。我們稱之為強(qiáng)歸納法，又叫串值歸納法。

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

　　可能依賴于以前各步時(shí)，一般應(yīng)選用強(qiáng)歸納法，下面舉例說明其應(yīng)用。

　　例 有數(shù)目相等的兩堆棋子，兩人輪流從任一堆里取幾項(xiàng)棋子，但不能

　　不取也不能同時(shí)從兩堆里取，規(guī)定凡取得最后一項(xiàng)者勝。求證后者必勝。

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

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

　　歸納 設(shè) Ｎ ｎ≤ｋ 時(shí)，乙必勝�，F(xiàn)證 ｎ＝ｋ＋ｌ 時(shí)也是乙必勝。

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

　　二種可能：

　�。ǎ保┤� ｒ＜ｋ，經(jīng)過兩人各取一次之后，兩堆都只有 ｋ－ｒ 顆，ｋ－ｒ＜ｋ，

　　現(xiàn)在又輪到甲先取，依歸納假設(shè)，乙必勝。

　�。ǎ玻┤� ｒ＝ｋ，顯然是乙勝，證畢。

　　上述形式的歸納法雖然比較簡(jiǎn)單，但如使用不當(dāng)，往往會(huì)發(fā)生錯(cuò)誤，有

　　兩點(diǎn)應(yīng)注意：第一，在使用歸納假設(shè)時(shí)防止無形中引入不相干的假設(shè)。第二，

　　在證明過程中應(yīng)注意數(shù)學(xué)規(guī)律的正確性。下面我們引入一個(gè)反例，在這個(gè)反

　　例中，由于錯(cuò)誤的證明導(dǎo)致證得了錯(cuò)誤的待證命題。

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

　　下面給出錯(cuò)誤的證明：

　　證：奠基 ｎ＝１ 時(shí)該命題成立。

　　歸納 利用強(qiáng)歸納法，可以有如下的歸納假設(shè)：任意 １ 條，２ 條，３ 條，…，

　�。� 條直線均重合成一條直線，要證 ｋ＋１ 條直線也重合成一條直線，設(shè)這 ｋ＋１

　　條直線為 ｌ１、ｌ２、…，ｌｋ，ｌｋ＋１ 由強(qiáng)歸納假設(shè)得 ｌ１，…，ｌｋ…重合為一條直線，

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

　　重合一條直線了。

　　細(xì)心的讀者也許已經(jīng)發(fā)現(xiàn)這里的錯(cuò)誤了，這是由于錯(cuò)誤地使用了強(qiáng)歸納

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

　　這一點(diǎn)把強(qiáng)歸納假設(shè)使用錯(cuò)了。強(qiáng)歸納假設(shè)中并沒有包含這一條件，因?yàn)槲?/p>

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

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

　　實(shí)際上是要求 ｋ≥２，這就是錯(cuò)誤的所在。

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

　　用數(shù)學(xué)歸納法證明 Ｐ（ｕ，ｎ）對(duì)一切 ｎ 成立時(shí)，在奠基步中，應(yīng)證 Ｐ（ｕ，０）

　　對(duì)一切 ｕ 成立。在歸納步中，假設(shè) Ｐ（ｕ，ｋ）對(duì)一切 ｕ 成立，證明 Ｐ（ｕ，ｋ＋１）

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

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

　　例 求證當(dāng) ｎ≥３ 時(shí)有 ｎ（ｎ＋１）≥（ｎ＋１）３。

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

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

　　作參數(shù)），部分 ｎ 保持不變，即寫成

　�。睿酰睢荩ǎ酰�ｌ）ｎ，

　　則可用參變歸納法證明當(dāng) ｕ≥ｎ≥３ 時(shí)上式成立，原命題即可得證。

　　奠基 ｎ＝３ 時(shí)，對(duì) ｕ≥３ 的一切 ｕ 均有

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

　　≥ｕ３＋３ｕ＋ｇｕ

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

　�。剑ǎ酰�１）３＝右端

　　歸納 ｎ＝ｋ＋１ 時(shí)，

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

　�。剑ǎ酰� 十 ｕ）ｕｋ≥（ｕｋ 十 ｋ）Ｕｋ

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

　�。剑ǎ眨�ｌ）ｋ＋１＝右端。

　　所以當(dāng) ｕ≥ｎ≥３ 時(shí)，有 ｎｕｎ＞（ｕ＋ｌ）ｎ。

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

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

　　數(shù)變?cè)?ｎ，對(duì) ｎ 施行歸納，ｎ 稱為歸納變?cè)�，但是在�?shù)學(xué)的一些分支中，有些

　　待證命題表面上看來似乎不含自然數(shù)變?cè)?ｎ，但仔細(xì)一分析，實(shí)際上是含有

　　自然數(shù)變?cè)�的，�?dāng)我們一旦把 ｎ 的含義明確以后，用數(shù)學(xué)歸納法去證明這些

　　待證命題就迎刃而解了。舉一個(gè)簡(jiǎn)單的例子。

　　例 證明由｛ａ，ｂ，ｃ，ｄ｝四個(gè)標(biāo)識(shí)符利用＋、－運(yùn)算符組成的任意算術(shù)

　　表達(dá)式中，所含標(biāo)識(shí)符的個(gè)數(shù)一定等于這個(gè)表達(dá)式中運(yùn)算符的個(gè)數(shù)加 １。

　　證：設(shè)任意的表達(dá)式為 ｆ，而歸納變?cè)?ｎ 為 ｆ 中所含運(yùn)算符的個(gè)數(shù)。

　　奠基 ｎ＝０，則 ｆ 由一個(gè)標(biāo)識(shí)符組成（因?yàn)闆]有運(yùn)算符），所以命題成立。

　　歸納 假設(shè) ｎ≤ｋ 時(shí)本命題成立，現(xiàn)證 ｎ＝ｋ＋１ 時(shí)本命題也成立。 ｆ 一

　　定是下述兩種情況之一：

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

　　其中 ｆ１，ｆ２ 所含的運(yùn)算符個(gè)數(shù)都小于 ｋ＋ｌ，對(duì) ｆ１，ｆ２ 使用歸納假設(shè)，可

　　得 ｆ１＋ｆ２，ｆ１－ｆ２ 中所含標(biāo)識(shí)符個(gè)數(shù)也比各自所含的運(yùn)算符的個(gè)數(shù)多 １。

　�。ǎ矗�廣義歸納法。數(shù)學(xué)歸納法不僅可用于含有自然數(shù)變?cè)?ｎ 的命題，經(jīng)

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

　　于一個(gè)含有某個(gè)歸納集上的變?cè)?ｘ 的待證命題 Ｐ（ｘ），所用的歸納法稱之為

　　廣義歸納法。

　　定義：設(shè)有一個(gè)集合 Ａ，如果它滿足下面三個(gè)性質(zhì)：

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

　�。ǎ玻┤绻� ｘ 是 Ａ 中元素，則 ｆ１１（ｘ），ｆ１２（ｘ），…ｆ１ｎ１（ｘ）也是 Ａ 中

　　的元素（ｎ、＞０）；

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

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

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

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

　�。ǎ常�Ａ 中的元素僅限于此。

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

　　的生成函數(shù)（其中第一下標(biāo)為該函數(shù)的元素，第二下標(biāo)以區(qū)分具有同樣元素

　　的各函數(shù)）。

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

　�。ǎ�）＝ｘ＋１。

　　前例中集｛ａ，ｂ，ｃ，ｄ｝的元素利用“＋”，“－”運(yùn)算所構(gòu)成的一切表

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

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

　　在證明含有某個(gè)歸納集 Ａ 上的變?cè)?Ｘ 的待證命題 Ｐ（ｘ）時(shí)，可用如下的

　　廣義歸納法。

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

　　是 Ａ 中的開始元素。

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

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

　�。�ｉ））也成立。在例 ４ 中，因?yàn)楸磉_(dá)式所組成的集合是歸納集（記為 Ａ），

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

　　奠基：對(duì)于 Ａ 中的四個(gè)開始元素 ａ，ｂ，Ｃ，ｄ，因?yàn)樗鼈兊臉?biāo)識(shí)符個(gè)數(shù)為

　　１， 而運(yùn)算符個(gè)數(shù)均為 ０，所以命題成立。

　　歸納：對(duì)于 Ａ 中的元素 ｘ，ｙ，ｆ２１（ｘ，ｙ）＝ｘ＋ｙ 中，我們?cè)O(shè) ｘ＋ｙ 標(biāo)識(shí)

　　符個(gè)數(shù)為 ｍ，運(yùn)算符個(gè)數(shù)為 ｎ；

　�。� 中標(biāo)識(shí)符個(gè)數(shù)為 ｍｌ，運(yùn)算符個(gè)數(shù)為 ｎｌ；

　　ｘ 中標(biāo)識(shí)符個(gè)數(shù)為 ｍ２，運(yùn)算符個(gè)數(shù)為 ｎ２；

　　則

　�。恚剑恚欤�ｍ２＝（ｎ１＋１）＋（ｎ２＋１）

　�。ǎ睿欤�ｎ＋１）＋１＝ｎ＋１．

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

　　成立。

【數(shù)學(xué)歸納法證明的原理】相關(guān)文章：

關(guān)于血糖檢測(cè)的原理總結(jié)03-09

計(jì)算機(jī)的組成原理教案（精選16篇）10-22

釋放證明04-06

辦理停車泊位證明03-20

團(tuán)關(guān)系轉(zhuǎn)出證明02-25

經(jīng)理聘任證明五篇02-06

先進(jìn)雙聯(lián)戶事跡證明材料03-20

引產(chǎn)沒有證明的解決辦法03-19

雷鋒事跡證明材料（精選15篇）03-01

多邊形內(nèi)角和定理證明05-17