數學歸納法證明的原理

數學歸納法證明的原理

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

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

（１）ｌ 是自然數。

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

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

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

接後繼”數。

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

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

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

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

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

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

對任何 ｎ∈Ｎ 都成立。

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

以及它們的應用。

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

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

述。

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

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

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

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

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

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

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

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

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

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

二種可能：

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

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

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

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

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

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

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

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

下面給出錯誤的證明：

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

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

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

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

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

重合一條直線了。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ｎｕｎ≥（ｕ＋ｌ）ｎ，

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

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

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

≥ｕ３＋３ｕ＋ｇｕ

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

＝（ｕ＋１）３＝右端

歸納 ｎ＝ｋ＋１ 時，

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

定是下述兩種情況之一：

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

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

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

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

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

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

廣義歸納法。

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

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

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

的元素（ｎ、＞０）；

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

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

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

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

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

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

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

的各函數）。

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

（ｘ）＝ｘ＋１。

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

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

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

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

廣義歸納法。

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

是 Ａ 中的開始元素。

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

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

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

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

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

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

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

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

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

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

則

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

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

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

成立。