第3章 數學歸納法

前n項2的冪的和是多少？

像以往一樣，解決問題的第一步是確信你理解了問題的含義。什么是2的冪？形如2³（就是8），是2的指數為某個整數的結果。好了，那么n是什么？不用說，n是任意的使問題有意義的東西。問題是要把某些對象加起來，n是加在一起的對象的數量。所以n必須是一個表示全部量的變量，例如10。最后，我們需要確定前n項2的冪是哪些。第一項2的冪是2⁰，還是2¹，或者其他什么？在計算機科學中，我們通常從0開始計數。

知道了n的值，我們就可以計算出答案。例如，在n=10的情況下，問題是要求出下式的值：

2⁰+2¹+2²+2³+2⁴+2⁵+2⁶+2⁷+2⁸+2⁹

=1+2+4+8+16+32+64+128+256+512

答案是1023。

我們并不只是要對n=10的情況求和。問題是以變量n陳述的，所以我們希望答案的形式與該變量相關。換句話說，我們的答案應該是泛化的公式，對于任意n都適用。特別地，適用于下式：

2⁰+2¹+2²+…+2^n-1

求和的每個元素都稱為項（term），因此在上式中，2⁰,2¹,…,2^n-1都是項。注意：最后一項是2^n-1，而不是2ⁿ。我們是從0開始計數的，因此前n項2的冪是指2的0,1,2,…,n-1次冪，n項中的最后一項是2^n-1。

三個點…稱為省略號（ellipsis）。省略號給出了一種模式，表示對讀者是顯而易見的。但是“顯而易見”是心理感受，讀者未必會與作者有同樣的感受。如果我們只有如下公式：

省略的項顯而易見嗎？又省略了多少項呢？“顯而易見”不是事實。我們在之前確定了要討論對2的冪求和，如果只給你帶省略號的式（3-1），那么對缺失項的推斷就不止一種結果?？梢杂羞@樣的推斷：第二項比第一項大1，第三項比第二項大2，以此類推。在這種情況下，第四項應該比第三項大3，即7。那么結果可以是

而不是

1+2+4+8+16+32+…+512

需要弄清楚512是否真的是式（3-2）中的序列中的最后一個數（見習題3.10）。

避免上述情況中模糊含義的解決方法就是找到典型項的表達式，并且使用求和表示法來表示要相加的是哪些項。典型的2的冪看起來形如2ⁱ——我們需要一個不同于n的變量名作為指數，因為n已經被用來表示相加的項數。則上式中的前n項和可以無歧義地表示為

“∑”是大寫希臘字母sigma，表示求和。

與省略號表示法不同，求和表示法沒有留下任何其他想象的空間。即使在n=1或n=0的情況下，它也是有意義的。當n=1時，式（3-3）變為

即對第一項求和。當n=0時，求和的上限小于下限，此時式（3-3）變成對第0項求和，按照約定結果為0：

再舉一個例子，前n個奇數的和如何表示？奇數表示為2i+1，第一個奇數是1，即當i=0時2i+1的值。所以前n個奇數的和可以記為^[1]

現在回到本章開始的問題。我們能找到一個與式3-3等價的簡單公式（不帶省略號與求和符號）嗎？

面對這樣的問題（當你確定理解了問題之后），首先要做的是嘗試幾個例子，這有助于清楚你的理解為什么正確。在證明定理2.4時，使用了同樣的策略。先代入n=1，2，3，得到

1、3、7分別比2、4、8小1，它們的后繼數都是2的冪。在構造假設之前，最好再試一次：

15比16小1，是下一項2的冪。至此我們還沒有做什么證明，但是這種模式似乎太有規律而不像是巧合。我們來推測一下：

我們的推測對嗎？右側或許是2^n-1-1，也或許是2ⁿ⁺¹-1呢？再代入n=4來確認。在n=4的情況下，式（3-6）的左端與式（3-5）相同，即為15，而式（3-6）的右端為2⁴-1=15。所以，看起來式（3-6）是一個正確的推測。即使在n=0的情況下，它也是可行的：

左端i的結尾值小于i的開始值，是一個零項求和，即0。

這些還不足以成為一個證明。還需要進一步觀察從式（3-4）到式（3-5）是怎樣過渡的。也就是說，如果2³加到2³-1上，則右端是2³+2³-1=2·2³-1=2⁴-1。

一般來說“2的冪再加上其自身會得到其后繼2的冪”是成立的。所以假設我們已知式（3-6）對于一個給定的n是成立的。在歸納法中，這個假設被稱為歸納假設（induction hypothesis）。歸納法的關鍵步驟——歸納步驟（induction step）是證明如果歸納假設是真的，那么下一個值（用n+1替換了n）也是真的。下面是歸納步驟：

這正是用n+1替換n后，式（3-6）的結果。

這是數學歸納法證明（proof by mathematical induction）的一個經典示例。術語“歸納”的含義是指命題關于某一個值（例如n）為真，蘊含著該命題對n+1也為真，從而有命題對于任意值都為真，那么對于任意更大的值，也為真。與此相類似，如果我們有了一個萬無一失的方法可以從梯子的一級臺階登上更高一級臺階，那么我們就能夠到達第一級臺階之上的任何一級臺階（見圖3.1）。

這里給出數學歸納法證明的一般形式（見圖3.2）。

下面證明謂詞P（n）對于大于或等于某個特定數n₀的任意數n都成立：

歸納基礎。證明P（n₀）成立。

歸納假設。設任意n是大于或等于n₀的某個數，假設P（n）成立。

歸納步驟。假設歸納假設為真，證明P（n+1）成立。

應用上述模式證明式3-6的推測，隱去所有我們為找到通用謂詞而分析的特殊情況和猜想。

例3.8 對于任意的n≥0，

解：按照歸納模式，謂詞P（n）為

并且n₀=0。

歸納基礎。P（0）表示命題

成立，因為方程的左右兩端都等于0（參見式3-7）。

歸納假設。假設P（n）成立，即

對于任意選定的n值（n≥0）成立。

歸納步驟。我們需要證明P（n+1）成立，即

分離出最后一項為相加項，式（3-9）的左側為

其中項正好是歸納假設P（n），等于2ⁿ-1。因此，要完成式（3-9）的證明，我們只需要再證明

因為2ⁿ+2ⁿ=2ⁿ⁺¹，所以上式成立。■

數學歸納法是強有力的證明技術且應用廣泛，如下例所示。

例3.10 對于任意n≥0，有

解：設謂詞P（n）為

歸納基礎。令n₀=0，等式左端的和是空項，其值為0；右端表達式是，值也為0。即P（0）成立。

歸納假設。假設P（n）為

對于任意選定的n值（n≥0）成立。

歸納步驟。我們需要證明P（n+1）成立，即

再次將左端的最后一項分離為相加項，可以應用歸納假設如下：

有時，一個規范的證明不足以表達直覺的感受，因為我們不清楚做符號變換的原因。給出一個具體的解釋或許會更令人滿意。對于式（3-12）（以及許多其他求和問題）的幾何解釋是一個由黑灰色塊覆蓋的網格。

圖3.3就是當n=5時，式（3-12）的幾何表示。第一行有n個黑塊，下一行有n-1個黑塊，…，最后一行有1個黑塊。因此，黑塊的數量為。我們用另一種方法來計算它的值。網格的長為n+1，高為n，其中一半是黑塊（比較黑灰兩色的形狀，可以發現旋轉一下完全相同），所以黑塊的數量是矩形面積的一半，即。

對于歸納步驟，我們也可以給出相應的幾何解釋。歸納假設是。在歸納步驟中，我們增加了n+1個方塊，最后的總和是。圖3.4展示了一個（n+1）×（n+2）的網格，左上半部分為黑色和淺灰色，右下半部分為灰色。圖3.4中的黑色部分與圖3.3中的黑色部分完全匹配，黑色部分與增加的對角線上n+1個淺灰塊一起覆蓋了新的（n+1）×（n+2）網格的一半。

有時我們想表示一個序列值的乘積，而不是求和。乘積的表示法是用大寫希臘字母pi，即∏，它的作用類似于求和∑。例如，例1.6中的公式可以記為

如同求和中的元素被稱作項一樣，乘積中相乘的元素被稱為因子（factor）。上面乘積中的因子有，…，。

嘗試一下有關乘積命題的歸納模式。

例3.13 對于任意n≥1，有

舉例來說，在n=3的情況下，式（3-14）變換為

再變換一下形式更易于理解：

每個分數的分子與下一個分數的分母相等，所以除了最后一個分子，其他分子都被約掉了。應用歸納法可以證明這個論點。

解：設謂詞P（n）表示為

歸納基礎。n₀=1，式（3-15）為

成立，因為兩邊都等于2。

歸納假設。假設對于某個n≥1，P（n）成立，即

歸納步驟。進一步計算P（n+1），式（3-15）的左端變為

所證為真?！?/p>

若約定零個因子的乘積為1，那么等式（3-14）在n=0的情況下，也是有意義的，即

為什么這樣的約定是有意義的呢？在零項求和時我們有類似的約定，即它的和為0。憑直覺可知，如果在一些項求和的基礎上再加上零項，那么就等于加上了0。類似地，如果在一些因子乘積的基礎上再乘以零個因子，那么等同于乘以1。

歸納法也可用于證明數字之外的事物。在計算機科學中，我們經常會遇到由0和1構成的序列，稱0和1為兩個位（bit）^[2]，若干位的序列是一個二進制字符串（binarystring），也稱為位串（bitstring或bitofstring）。例如，10001001是一個長度（length）為8的字符串。一個位串的補（complement）是將1和0互換的結果。例如，10001001的補是01110110。兩個位串的串聯（concatenation）是指將一個位串接到另一個位串上，例如，10001001和111的串聯是10001001111。兩個位串串聯的長度是它們的長度之和，即8+3=11。

存在一個有趣的位串序列被稱作Thue序列（Thuesequence^[3]），定義如下：

T₀=0，對于任意的n≥0，

T_n+1=T_n與T_n補的串聯

這是一個歸納定義（inductive definition）[也稱為遞歸定義（recursive definition）]的示例。T₀定義為基礎實例（base case），而用T_n來定義的T_n+1是構造實例（constructor case）。我們來看看Thue序列前幾個字符串的定義。

0.T₀=0，這是基礎實例。

1.T₁是將T₀（即0）與T₀的補（即1）串聯，所以T₁=01。

2.T₂是將T₁（即01）與T₁的補（即10）串聯，所以T₂=0110。

3.T₃是將T₂（即0110）與T₂的補（即1001）串聯，所以T₃=01101001。

4.T₄是將T₃（即01101001）與T₃的補（即10010110）串聯，所以T₄=0110100110010110。

對于任意的n≥0，T_n是T_n+1的前半部分，因此我們可以定義一個無窮位串t₀t₁t₂…，其中t_i是T_n的第i位，且所有的n都足夠大，使得T_n至少有i位。例如，當i=4時，T₀、T₁和T₂的長度少于5位。但是對于所有的n≥3都有T_n的長度至少為5，并且它們具有相同的第5位，即t₄都是1。

Thue序列具有某些非常有趣的性質。它看上去像是重復的，但并不重復；它看上去像是隨機的，但并不是隨機的。我們用數學歸納法來證明幾個簡單的性質。

例3.16 對于任意的n≥0，T_n的長度是2ⁿ。

解：我們應用歸納法來證明這一點。

歸納基礎。n₀=0，T_n0=T₀=0，其長度為1=2⁰=2^n₀。

歸納假設。假設T_n的長度是2ⁿ。

歸納步驟。T_n+1是由T_n與其補串聯而成，而這兩個字符串的長度都是2ⁿ，所以T_n+1的長度是2ⁿ+2ⁿ=2ⁿ⁺¹?！?/p>

例3.17 對于任意的n≥1，T_n以01開頭，如果n是奇數，則以01結尾；如果n為偶數，則以10結尾。

解：T₁=01，所以對于每個n≥1，都有T_n的前兩位是01。下面應用歸納法證明怎樣得到T_n的結尾。

歸納基礎。n₀=1。1是奇數，并且有T_n0=T₁=01，即以01結尾。

歸納假設。對于某個n≥1，假設當n為奇數時，T_n以01結尾；當n為偶數時，則以10結尾。

歸納步驟。T_n+1是以T_n最后兩位的補結束，如果n為奇數，則n+1為偶數；如果n是偶數，則n+1為奇數。因此，如果n+1是奇數，則T_n+1以01結尾；如果n+1為偶數，則T_n+1以10結尾。■

例3.18 對于任意的n≥0，T_n中連續的0或連續的1永遠不會多于兩個。

解：T₀只有一位，所以命題對于T₀是成立的。我們從n₀=1開始使用歸納法。

歸納基礎。n₀=1。那么T_n0=T₁=01，由于沒有連續的相同位，因此肯定沒有連續的相同位超過兩個。

歸納假設。對于某個n≥1，假設T_n中不存在超過兩個連續的相同位。

歸納步驟。T_n+1的前半部分來自T_n，后半部分來自T_n的補。根據歸納假設，兩者中都沒有000或111。因此，如果其中之一的任何情況發生，必然出現在連接處，即一個位串包含兩位，另一個位串包含一位。而根據例3.17可知，在連接處的四位只能是0110或1010，這兩種情況都不包含連續三個相同位（見圖3.5）?！?/p>

我們將在習題3.11和習題11.11中再討論Thue序列的其他性質。

我們可以用數學歸納法來證明鴿籠原理（第1章）。這需要變通一下，因為鴿籠原理中沒有提到可以進行歸納的特定數字n，通常，我們稱之為歸納變量（induction variable），在前面的歸納示例中用n來表示。

例3.19 如果有f：X→Y并且|X|>|Y|，那么存在元素x₁，x₂∈X，使得x₁≠x₂且f(x₁)=f(x₂)。

解：為了能夠用歸納法證明，我們必須要確定歸納變量。這里有兩種比較明顯的可能：集合X的大小和集合Y的大小。兩者都可以用，但證明會有所不同。讓我們對|X|進行歸納，并重申：對于任意的n≥2，P（n）都為真，其中P（n）表示

對于任意有窮集|X|和|Y|，其中|X|＞Y，并且X=n，如果有f：X→Y，則存在不同的元素x₁，x₂∈X，使得f（x₁）=f（x₂）。

習題3.2使用了Y的大小（而不是X的大?。┳鳛闅w納變量。

歸納基礎。n₀=2。如果|X|＞|Y|且X=2，并且存在一個從X到Y的函數f，那么Y必須等于1。首先，Y必須包含至少一個元素，因為對于每個x∈X，有f（x）∈Y；其次，Y不能包含多于1個元素，原因是|Y|＜|X|。從而，X的兩個元素必須都映射到Y的唯一元素，得證。

歸納假設。假設對于任意的某個n≥2，X和Y為任意有窮集，使得|X|>|Y|和|X|=n，如果有f:X→Y，則存在不同的元素x₁,x₂∈X，使得f(x₁)=f(x₂)。

歸納步驟。我們要證明的是：如果|X|>|Y|和|X|=n+1，并且f:X→Y，則存在不同的元素x₁,x₂∈X，使得f(x₁)=f(x₂)。

任選元素x∈X，有兩種可能（接下來是情況分析）。要么存在另一個元素x′∈X，使得x′≠x，但是f（x′）=f（x）；要么不存在這樣的x′。第一種情況見圖3.6，歸納步驟成立，我們找到了X的兩個不同元素都映射到Y的同一元素。在第二種情況中，x是集合X中f的值為f（x）的唯一一個元素（見圖3.7）。設X′是從X中去除x后得到的集合，Y′是從Y中去除f（x）后得到的集合?，F在有|X′|=n且|Y′|=Y-1＜n，應用歸納假設。f′：X′→Y′是一個從大小為n的集合到更小集合上的函數，對于X′中的元素，f′與f的函數值相同。由歸納假設可得存在不同的元素x₁，x₂∈X，使得f′（x₁）=f′（x₂）∈Y′。那么x₁和x₂也是X的不同成員，且具有相同的f值?！?/p>