數學(xué)歸納法證明的原理
數學(xué)歸納法證明的原理
數學(xué)歸納法證明的原理
數學(xué)歸納法證明的是與自然數有關(guān)的命題，它的依據是皮亞諾提出的自
然數的序數理論，就是通常所說(shuō)的自然數的皮亞諾公理，內容是：
�。ǎ保� 是自然數。
�。ǎ玻┟總€(gè)自然數 ａ 有一個(gè)確定的“直接后繼”數 ａ’，ａ 也是自然數。
�。ǎ玻帷伲�，即 １ 不是任何自然數的“直接后繼”數。
�。ǎ矗┯� ａ’＝ｂ’，推得 ａ＝ｂ，即每個(gè)自然數只能是另外的唯一自然的“直
接后繼”數。
�。ǎ担┤我蛔匀粩档募�，如果包含 １，并且假設包含 ａ，也一定包含 ａ
的“直接后繼”數 ａ’，則這個(gè)集合包含所有的自然數。
皮亞諾公理中的（５）是數學(xué)歸納法的依據，又叫歸納公理
數學(xué)歸納法的應用及舉例。
因為由假設知 ４２ｋ＋１＋３ｋ＋２ 能被 １３ 整除，１３４２ｋ＋１ 也能被 １３ 整除，這就
是說(shuō)，當 ｎ＝ｋ＋１ 時(shí)，ｆ（ｋ＋ｌ）能被 １３ 整除。根據（１）、（２），可知命題
對任何 ｎ∈Ｎ 都成立。
下面按歸納步中歸納假設的形式向讀者介紹數學(xué)歸納法的幾種不同形式
以及它們的應用。
�。ǎ欤┖�(jiǎn)單歸納法。即在歸納步中，歸納假設為“ｎ＝ｋ 時(shí)待證命題成立”。
這是最常用的一種歸納法，稱(chēng)為簡(jiǎn)單歸納法，大家都比較熟悉，這里不再贅
述。
�。ǎ玻⿵姎w納法。這種數學(xué)歸納法，在歸納步中，其歸納假設為“ｎ≥ｋ
時(shí)待證命題成立”。我們稱(chēng)之為強歸納法，又叫串值歸納法。
通常，如果在證明 ｐ（ｎ＋ｌ）成立時(shí)，不僅依賴(lài)于 ｐ（ｎ）成立，而且還
可能依賴(lài)于以前各步時(shí)，一般應選用強歸納法，下面舉例說(shuō)明其應用。
例 有數目相等的兩堆棋子，兩人輪流從任一堆里取幾項棋子，但不能
不取也不能同時(shí)從兩堆里取，規定凡取得最后一項者勝。求證后者必勝。
證：歸納元 ｎ 為每堆棋子的數目。設甲為先取者，乙為后取者。
奠基 ｎ＝ｌ，易證乙必勝。
歸納 設 Ｎ ｎ≤ｋ 時(shí)，乙必勝�，F證 ｎ＝ｋ＋ｌ 時(shí)也是乙必勝。
設甲在某堆中先取 ｒ 顆，Ｏ＜ｒ≤ｋ。乙的對策是在另一堆中也取 ｒ 顆。有
二種可能：
�。ǎ保┤� ｒ＜ｋ，經(jīng)過(guò)兩人各取一次之后，兩堆都只有 ｋ－ｒ 顆，ｋ－ｒ＜ｋ，
現在又輪到甲先取，依歸納假設，乙必勝。
�。ǎ玻┤� ｒ＝ｋ，顯然是乙勝，證畢。
上述形式的歸納法雖然比較簡(jiǎn)單，但如使用不當，往往會(huì )發(fā)生錯誤，有
兩點(diǎn)應注意：第一，在使用歸納假設時(shí)防止無(wú)形中引入不相干的假設。第二，
在證明過(guò)程中應注意數學(xué)規律的正確性。下面我們引入一個(gè)反例，在這個(gè)反
例中，由于錯誤的證明導致證得了錯誤的待證命題。
反倒：證明任意 ｎ 條直線(xiàn)均能重合成一條直線(xiàn)。
下面給出錯誤的證明：
證：奠基 ｎ＝１ 時(shí)該命題成立。
歸納 利用強歸納法，可以有如下的歸納假設：任意 １ 條，２ 條，３ 條，…，
�。� 條直線(xiàn)均重合成一條直線(xiàn)，要證 ｋ＋１ 條直線(xiàn)也重合成一條直線(xiàn)，設這 ｋ＋１
條直線(xiàn)為 ｌ１、ｌ２、…，ｌｋ，ｌｋ＋１ 由強歸納假設得 ｌ１，…，ｌｋ…重合為一條直線(xiàn)，
記為 ｌ。又由強歸納假設得 ｌ 和 ｌｋ＋１ 重合為一條直線(xiàn)，于是任意 ｎ 條直線(xiàn)便
重合一條直線(xiàn)了。
細心的讀者也許已經(jīng)發(fā)現這里的錯誤了，這是由于錯誤地使用了強歸納
假設而造成的。具體地說(shuō)，這是在“ｌ 和 ｌｋ＋１ 這兩條直線(xiàn)重合為一條直線(xiàn)”
這一點(diǎn)把強歸納假設使用錯了。強歸納假設中并沒(méi)有包含這一條件，因為我
們這里奠的基是 ｎ＝ｌ，因此待證命題“ｋ＋１ 條直線(xiàn)重合為一條直線(xiàn)”要求對于
一切大于等于 １ 的 ｋ 成立，而上面證明中所假設的 ｌ 和 ｌｋ＋１ 重合為一條直線(xiàn)
實(shí)際上是要求 ｋ≥２，這就是錯誤的所在。
�。ǎ常﹨⒆儦w納法。在待證命題中含有參數的時(shí)候，例如 Ｐ（ｕ，ｎ），則
用數學(xué)歸納法證明 Ｐ（ｕ，ｎ）對一切 ｎ 成立時(shí)，在奠基步中，應證 Ｐ（ｕ，０）
對一切 ｕ 成立。在歸納步中，假設 Ｐ（ｕ，ｋ）對一切 ｕ 成立，證明 Ｐ（ｕ，ｋ＋１）
對一切 ｕ 成立。這里，“Ｐ（ｕ，ｋ）”對一切 ｕ 成立稱(chēng)之為參變歸納假設，這
種證明方法叫做參變歸納法，Ｕ 起著(zhù)參數的作用。
例 求證當 ｎ≥３ 時(shí)有 ｎ（ｎ＋１）≥（ｎ＋１）３。
本題證明的困難主要在于歸納步驟，無(wú)論采用哪種歸納假設，都難于證
明。如果我們對該待證命題施展一定的技巧，把該式中的部分 ｎ 寫(xiě)成 ｕ（視
作參數），部分 ｎ 保持不變，即寫(xiě)成
�。睿酰睢荩ǎ酰欤�，
則可用參變歸納法證明當 ｕ≥ｎ≥３ 時(shí)上式成立，原命題即可得證。
奠基 ｎ＝３ 時(shí)，對 ｕ≥３ 的一切 ｕ 均有
右端＝３ｕ３＝ｕ３＋ｕｕ２ｕ
≥ｕ３＋３ｕ＋ｇｕ
�。荆酰常常酰玻常酰�
�。剑ǎ酰保常接叶�
歸納 ｎ＝ｋ＋１ 時(shí)，
左端＝（ｋ＋１）Ｕｋ＋１＝ｕ（ｋ＋１）ｕｋ
�。剑ǎ酰� 十 ｕ）ｕｋ≥（ｕｋ 十 ｋ）Ｕｋ
�。剑耄ǎ酰欤酰搿荩ǎ睿保ǎ酰保�
�。剑ǎ眨欤耄保接叶�。
所以當 ｕ≥ｎ≥３ 時(shí)，有 ｎｕｎ＞（ｕ＋ｌ）ｎ。
令 ｕ＝ｎ，上式便為 ｎｎ＋１≥（ｎ＋ｌ）ｎ，即為原不等式，故原不等式得證。
值得指出的是，上面三種形式的數學(xué)歸納法，都要求待證命題含有自然
數變元 ｎ，對 ｎ 施行歸納，ｎ 稱(chēng)為歸納變元，但是在數學(xué)的一些分支中，有些
待證命題表面上看來(lái)似乎不含自然數變元 ｎ，但仔細一分析，實(shí)際上是含有
自然數變元的，當我們一旦把 ｎ 的含義明確以后，用數學(xué)歸納法去證明這些
待證命題就迎刃而解了。舉一個(gè)簡(jiǎn)單的例子。
例 證明由｛ａ，ｂ，ｃ，ｄ｝四個(gè)標識符利用＋、－運算符組成的任意算術(shù)
表達式中，所含標識符的個(gè)數一定等于這個(gè)表達式中運算符的個(gè)數加 １。
證：設任意的表達式為 ｆ，而歸納變元 ｎ 為 ｆ 中所含運算符的個(gè)數。
奠基 ｎ＝０，則 ｆ 由一個(gè)標識符組成（因為沒(méi)有運算符），所以命題成立。
歸納 假設 ｎ≤ｋ 時(shí)本命題成立，現證 ｎ＝ｋ＋１ 時(shí)本命題也成立。 ｆ 一
定是下述兩種情況之一：
�。� 是 ｆ１＋ｆ２ 或 ｆ 是 ｆ１－ｆ２。
其中 ｆ１，ｆ２ 所含的運算符個(gè)數都小于 ｋ＋ｌ，對 ｆ１，ｆ２ 使用歸納假設，可
得 ｆ１＋ｆ２，ｆ１－ｆ２ 中所含標識符個(gè)數也比各自所含的運算符的個(gè)數多 １。
�。ǎ矗⿵V義歸納法。數學(xué)歸納法不僅可用于含有自然數變元 ｎ 的命題，經(jīng)
推廣后，還可用于含有某些其它集合上的命題。這種集合，稱(chēng)為歸納集。對
于一個(gè)含有某個(gè)歸納集上的變元 ｘ 的待證命題 Ｐ（ｘ），所用的歸納法稱(chēng)之為
廣義歸納法。
定義：設有一個(gè)集合 Ａ，如果它滿(mǎn)足下面三個(gè)性質(zhì)：
�。ǎ保幔�，ａ２…，ａｎ 是 Ａ 中的元素（ｎ≥１）；
�。ǎ玻┤绻� ｘ 是 Ａ 中元素，則 ｆ１１（ｘ），ｆ１２（ｘ），…ｆ１ｎ１（ｘ）也是 Ａ 中
的元素（ｎ、＞０）；
如果 ｘ，ｙ 是 Ａ 是元素，則 ｆ２１（ｘ、ｙ），ｆ２２（ｘ，ｙ），…ｆ２ｎ２（ｘ，ｙ）
也是 Ａ 中元素（ｎ２＞０）；…；
如果 ｘ１…，ｘｍ 是 Ａ 中元素，則 ｆｍ１ ｘｌ…ｘｍ），ｆｍ２（ｘｌ…，ｘｍ），…ｆｍｎｍ
�。ǎ薄�，ｘｍ）也是 Ａ 中元素（ｍ≥ｌ，ｎｍ＞０）。
�。ǎ常� 中的元素僅限于此。
則 Ａ 稱(chēng)之為歸納集 ａ１，ａ２，…ａｎ 稱(chēng)為該集的開(kāi)始元素，諸 ｆｉｊ 稱(chēng)為該集
的生成函數（其中第一下標為該函數的元素，第二下標以區分具有同樣元素
的各函數）。
按照上述的定義，自然數集是歸納集，它的開(kāi)始元素是 ０，生成函數是 ｆ
�。ǎ剑�。
前例中集｛ａ，ｂ，ｃ，ｄ｝的元素利用“＋”，“－”運算所構成的一切表
達式的集合是歸納集，開(kāi)始元素是是 ａ，ｂ，ｃ，ｄ，生成函數為 ｆ２１（ｘ，ｙ）
�。剑�，ｆ２２（ｘ，ｙ）＝ｘ－ｙ。
在證明含有某個(gè)歸納集 Ａ 上的變元 Ｘ 的待證命題 Ｐ（ｘ）時(shí)，可用如下的
廣義歸納法。
奠基步要證明（ａｌ），Ｐ（ａ２），……Ｐ（ａｎ）成立，這里 ａｌ，ａ２…，ａｎ
是 Ａ 中的開(kāi)始元素。
歸納法要證明對于 １≤ｉ≤ｍ 及 １≤ｊ≤ｎ 的所有 ｉ、ｊ 對于 Ａ 中的任何元
素 ｘ１，ｘ２…，ｘｉ，如果 Ｐ（ｘｌ），Ｐ（ｘ２），…，Ｐ（ｘ１）成立，則 Ｐ（ｆｉｊ（ｘｘ１，…，
�。椋┮渤闪�。在例 ４ 中，因為表達式所組成的集合是歸納集（記為 Ａ），
我們可用廣義歸納法證之。
奠基：對于 Ａ 中的四個(gè)開(kāi)始元素 ａ，ｂ，Ｃ，ｄ，因為它們的標識符個(gè)數為
�。�， 而運算符個(gè)數均為 ０，所以命題成立。
歸納：對于 Ａ 中的元素 ｘ，ｙ，ｆ２１（ｘ，ｙ）＝ｘ＋ｙ 中，我們設 ｘ＋ｙ 標識
符個(gè)數為 ｍ，運算符個(gè)數為 ｎ；
�。� 中標識符個(gè)數為 ｍｌ，運算符個(gè)數為 ｎｌ；
�。� 中標識符個(gè)數為 ｍ２，運算符個(gè)數為 ｎ２；
則
�。恚剑恚欤恚玻剑ǎ睿保保ǎ睿玻保�
�。ǎ睿欤睿保保剑睿保�
同理可證 ｆ２２（ｘ，ｙ）＝ｘ－ｙ 也有如上的結果，故依廣義歸納法，本命題
成立。
【數學(xué)歸納法證明的原理】相關(guān)文章：
關(guān)于血糖檢測的原理總結03-09
計算機的組成原理教案（精選16篇）10-22
釋放證明04-06
辦理停車(chē)泊位證明03-20
團關(guān)系轉出證明02-25
經(jīng)理聘任證明五篇02-06
先進(jìn)雙聯(lián)戶(hù)事跡證明材料03-20
雷鋒事跡證明材料（精選15篇）03-01
多邊形內角和定理證明05-17
