歸納法：如何從有限步驟保證無限多個整數命題

適用入口／先備／邊界

適用入口：十年級共同課程。本篇要理解「起點成立」與「成立性可以傳到下一步」，為何能共同保證一整條整數鏈上的命題。

本篇技能：

以第一型數學歸納法證明遞迴相關命題。

必要先備：能區分項序 $n$ 與第 $n$ 項 $a_{n}$ ；能讀懂起始值及「由前一項得到下一項」的遞迴式；能做代入、分配律與完全平方展開。第五節另會用到指數運算性質 $2^{k + 1} = 2 \cdot 2^{k}$ 。「命題」「假設」「如果……則……」會在本文就地說明，不要求先學完整的形式邏輯。

範圍邊界：只使用第一型數學歸納法，完整交代基礎步、歸納假設、歸納步與結論範圍。不證明不等式型歸納命題，不使用第二型或強歸納法，不展開求和公式、等比級數、和號、數列極限或無窮級數。歷史與程式情境用來理解這個概念的作用，不另增加組合學或程式設計的考核要求。

學完後應能做到：面對一個遞迴命題，清楚寫出要證明的 $P (n)$ 與起始整數 $n_{0}$ ；先證 $P (n_{0})$ ，再對任意合法的 $k$ 明示假設 $P (k)$ ，用已知條件推出 $P (k + 1)$ ，最後明確說明結論對所有整數 $n \geq n_{0}$ 成立，而不是只列幾個相符的數值。

一、形成的問題：知道下一層怎麼算，還不等於知道每一層都成立

數學裡有兩種很不一樣的工作。

一種是：給你目前的數，算出下一個數。另一種是：證明不論走到多後面，某個性質都不會失效。

前者是一個計算問題；後者是一個普遍性的問題。

以巴斯卡在 1654 年前後研究、1665 年出版的《算術三角形論》為一個可核對的歷史節點。在這之前，算術三角形及其中許多數量關係已經受到研究；他的工作並不是在一片空白中第一次算出那些數，而是把已知的主要性質組織成系統性的推導。這裡選取的是歸納推理明確呈現於著作中的一個節點，不把它說成唯一的發明時刻。維基文庫

在這種數表中，可以利用相鄰格數相加的規則繼續填數。但「能算出下一層」和「某種比例在所有層都成立」，仍是不同的要求。多寫幾層，可以檢查更多例子；可是，只要理由仍停留在那些例子，表外的情況就還沒有得到保證。

這不是單純的「算得太慢」。即使計算完全沒有錯，有限張表也不會自動變成一個涵蓋所有層的證明。

這裡區分的是兩種論證的能力，並不是說前人只會列表、不會證明。對一個涵蓋任意整數位置的主張，增加已檢查的例子，與提出能涵蓋全部位置的理由，是不同的工作。

巴斯卡在第十二項推論中，處理同一組格子內相鄰格數的比例。他把論證分成兩件事：先確認這個性質在第二層成立，再證明只要它在任意一層成立，就必定在下一層成立。這裡的「層」對應原作的 base；在他的方格排列中，它是斜向的一組格子，不是直接把一條水平列稱為一層。第二層連到第三層，第三層連到第四層，便不再只是依照外觀猜下去。維基文庫

這項改變的作用，也能在同一部著作中看到。書中最後提出：已知一格的兩個位置編號，能否不先把整張三角形逐格填完，就求出那一格的數？巴斯卡利用已證明的相鄰比例，逐次連接到數值已知的邊格，完成這項推導。先證成的一般關係，成了後續計算的依據，而不是只適用於紙上已列出的幾格。維基文庫

從這個節點可以看見歸納法的核心突破：

不必分別為每個整數寫一份不同的證明；可以先建立一個起點，再建立一條不受特定項序限制的傳遞規則。

它也有明確的限制：起點必須真的成立，傳遞規則必須真的證出來。少了其中任何一個條件，都不能靠「照這樣下去」補足。

二、看見 $1, 4, 9$ ，究竟知道了什麼？

先看一個教學例子。

有人告訴你：

a_{1} = 1, a_{2} = 4, a_{3} = 9 .

你很容易想到平方數，於是猜測：

a_{n} = n^{2} .

這是一個合理的猜想，但還不是證明。

問題不在於前三次計算有沒有算對，而在於：題目目前只告訴我們三個值，並沒有規定後面的項一定依照平方數繼續。

例如，另設一個規則：

b_{n} = n^{2} + (n - 1) (n - 2) (n - 3), n \geq 1, n 為整數 .

這裡的 $n$ 是項序， $b_{n}$ 是另一個規則在第 $n$ 個位置給出的數。

當 $n = 1, 2, 3$ 時，後面那個乘積都含有一個零因數，所以

b_{1} = 1, b_{2} = 4, b_{3} = 9 .

但是到了第四項，

\begin{aligned} b_{4} & = 4^{2} + (4 - 1) (4 - 2) (4 - 3) \\ = 16 + 6 \\ = 22, \end{aligned}

並不是 $16$ 。

因此，前三項相同，並不能排除第四項開始不同的規則。

這個反例沒有證明「原來的數列一定不是平方數」，也沒有證明「原來的第四項一定是 $22$ 」。它證明的是：單憑前三項，資訊還不足以保證平方數猜想永遠正確。

現在，把問題補完整。假設題目給的是：

a_{1} = 1, a_{n + 1} = a_{n} + 2 n + 1 對每個整數 n \geq 1 .

這就不再只是三個觀察值，而是起始值加上一條對所有合法項序都適用的更新規則。

我們可以算出

a_{2} = 1 + 3 = 4, a_{3} = 4 + 5 = 9,

仍然猜測 $a_{n} = n^{2}$ 。但這次有了可以用來證明的條件：每一步必須增加 $2 n + 1$ 。

剛才的 $b_{n}$ 並不符合這條遞迴式。因為在 $n = 3$ 時，遞迴式要求下一項是

9 + 2 \cdot 3 + 1 = 16,

而不是 $22$ 。

所以，我們要做的不是把相符的例子繼續排下去，而是回答：

假如第 $k$ 項確實是 $k^{2}$ ，這條遞迴規則是否一定會把下一項變成 ${(k + 1)}^{2}$ ？

這正是歸納步要處理的問題。

三、第一型數學歸納法：證明起點，再證明傳遞

1. 先把「要證明什麼」寫清楚

以 $P (n)$ 表示一個與整數 $n$ 有關、在所討論範圍內可以判斷真假的敘述。

例如：

P (n) ： a_{n} = n^{2} .

這裡的 $P (n)$ 不是數列的某一項，也不是一個待計算的數值；它代表「第 $n$ 項等於 $n^{2}$ 」這個命題。

再指定一個固定的起始整數 $n_{0}$ 。我們要處理的命題依序是

P (n_{0}), P (n_{0} + 1), P (n_{0} + 2), \dots

第一型數學歸納法要求完成兩件事。

基礎步：直接證明 $P (n_{0})$ 成立。

歸納步：對任意整數 $k \geq n_{0}$ ，明示假設 $P (k)$ 成立，再由這個假設及題目已知條件，證明 $P (k + 1)$ 成立。

兩者完成後，就能得出：

對所有整數 n \geq n_{0}, P (n) 都成立。

這種「基礎步加上任意相鄰一步」的形式，就是本篇使用的第一型數學歸納法。起點、索引範圍和歸納假設都必須明示，不能讓讀者自行猜測。康乃爾大學計算機科學系

起點不一定是 $1$ 。它也可以是 $0$ 或題目指定的其他整數；但命題必須在那些位置有定義，並且要從相應的起點實際完成基礎步。不能把一份從 $1$ 開始的證明，直接改寫結論成從 $0$ 開始。

2. 「假設成立」為什麼不是偷用答案？

這裡最容易產生疑問：

既然還不知道 $P (k)$ 是不是真的，為什麼可以假設它成立？

因為歸納步要證明的，並不是「所有 $P (k)$ 已經成立」，而是這個推論：

P (k) ⟹ P (k + 1) .

符號 $⟹$ 的意思是：如果左邊成立，就能推出右邊成立。

因此，歸納步中的假設是暫時的前提。你要展示的是：在這個前提之下，利用已知規則，下一步必然成立。

真正讓整條鏈開始運作的，是另外證明的基礎步：

\underset{已證明}{\underset{⏟}{P (n_{0})}} ⟹ P (n_{0} + 1) ⟹ P (n_{0} + 2) ⟹ \dots

基礎步提供第一個已知成立的命題；歸納步則保證成立性不會在往下一個整數前進時中斷。

這和直接假設「對所有 $n$ 都成立」完全不同。後者已經把整個待證結論當成前提；前者只是在建立一條有條件的、可以重複使用的推理。

3. 為什麼有限篇幅可以涵蓋無窮多個整數？

關鍵在於「任意 $k$ 」，而不是「某一個 $k$ 」。

假如你只驗證從 $k = 3$ 可以走到 $k = 4$ ，那就只建立了一條特定的連接。真正的歸納步必須不依賴 $k = 3$ 的特殊性，而是對每個合法的 $k$ 都有效。

現在，任取一個整數 $N \geq n_{0}$ 。

從 $n_{0}$ 到 $N$ ，只需要前進

N - n_{0}

次。這是有限次。因此，基礎步與同一條傳遞規則，足以保證 $P (N)$ 。

當 $N = n_{0}$ 時，所需的傳遞次數是 $0$ ；這個位置直接由基礎步保證。

而 $N$ 並沒有被限制成某個特定的整數。你指定哪一個合法的 $N$ ，這套理由都適用。

歸納法不是在有限時間內做完無窮多次驗算，而是用有限篇幅寫出一套對每個指定整數都適用的證明。

也因此，省略號並不代表最後還有一個叫作「無窮大」的整數等著被驗證。這個方法處理的是從起點出發、逐一增加 $1$ 的整數位置；它不會因此證明非整數位置上的敘述，也不會自動證明起點以前的情況。

無窮多個位置，靠的是同一條可反覆使用的推理，不是靠一張真的畫到無窮遠的圖。

數學歸納法的整數鏈：已證起點 P(n₀)，再由 P(k) 推到 P(k+1)，逐步涵蓋之後的整數。 — 「基礎步提供已成立的起點，歸納步保證任意相鄰位置間都能傳遞成立性。每個指定的整數位置，都只需要有限次傳遞；省略號不代表另有一個需要驗證的無窮大位置。」

四、完整示例：把遞迴生成的數列證明為平方數

已知

a_{1} = 1, a_{n + 1} = a_{n} + 2 n + 1 對每個整數 n \geq 1 .

證明：

a_{n} = n^{2} 對所有整數 n \geq 1 .

基礎步：確認第一個位置

令

P (n) ： a_{n} = n^{2} .

當 $n = 1$ 時，由題目給定的起始值，

a_{1} = 1 = 1^{2} .

所以 $P (1)$ 成立。

注意，這一步依靠的是題目給的 $a_{1} = 1$ ，不是把尚未證明的通項公式代回去，然後說公式符合自己。

歸納步：確認任意相鄰位置都能接上

取任意整數 $k \geq 1$ ，假設 $P (k)$ 成立，也就是

a_{k} = k^{2} .

接下來的目標是證明

a_{k + 1} = {(k + 1)}^{2} .

從已知的遞迴式出發：

\begin{aligned} a_{k + 1} & = a_{k} + 2 k + 1 \\ = k^{2} + 2 k + 1 \\ = {(k + 1)}^{2} . \end{aligned}

第一個等號使用題目給定的遞迴式。第二個等號才使用歸納假設 $a_{k} = k^{2}$ 。最後一個等號使用完全平方公式。

因此，只要 $P (k)$ 成立， $P (k + 1)$ 就成立。而且以上推理對任意整數 $k \geq 1$ 都適用。

封閉結論：說清楚涵蓋哪些整數

因為 $P (1)$ 成立，而且對任意整數 $k \geq 1$ ，都有

P (k) ⟹ P (k + 1),

所以由第一型數學歸納法，

a_{n} = n^{2} 對所有整數 n \geq 1 成立。

結論中的「所有整數 $n \geq 1$ 」不能省略成含糊的「所以成立」。它指出了起點與傳遞規則共同覆蓋的範圍。

為什麼遞迴式恰好增加 $2 k + 1$ ？

代數上，

{(k + 1)}^{2} - k^{2} = 2 k + 1 .

這說明相鄰平方數的差，恰好就是遞迴式規定的增加量。

也可以用單位方格理解。把一個 $k \times k$ 的正方形擴成 $(k + 1) \times (k + 1)$ 的正方形，可以先在右側增加一條含 $k$ 格的直條，再在上方增加一條含 $k + 1$ 格的橫條。

右上角那一格算在上方橫條裡，沒有重複計數。因此新增的格數是

k + (k + 1) = 2 k + 1 .

舊方格加上新增方格，便得到

k^{2} + k + (k + 1) = {(k + 1)}^{2} .

固定尺寸的圖只是示意；真正通用的是對任意正整數 $k$ 都成立的分塊理由。

平方數增量：原有九格，加右側三格與上方四格，成為十六格；9+3+4=16。 — 「以 $k = 3$ 示意：原有 9 格，右側增加 3 格，上方增加 4 格，合成 16 格。對任意正整數 $k$ ，同樣的分塊方式增加 $k + (k + 1) = 2 k + 1$ 格；右上角只計入上方橫條。固定尺寸的圖不是以單一案例代替一般證明。」

回查：公式與題目條件是否一致？

先查起始值：

1^{2} = 1 = a_{1} .

再查相鄰項的差：

{(n + 1)}^{2} - n^{2} = 2 n + 1,

確實符合遞迴式。最後代入一個具體位置：

a_{4} = a_{3} + 7 = 9 + 7 = 16 = 4^{2} .

這些回查能幫助我們抓到起點、索引或展開上的錯誤。但最後這次 $n = 4$ 的驗算，不是整個證明成立的理由；普遍性的保證，已經由任意 $k$ 的歸納步建立。

五、起點不一定是 $1$ ：結論要跟著起點走

再看一個自設的教學例子。

已知

u_{3} = 7, u_{n + 1} = 2 u_{n} + 1 對每個整數 n \geq 3 .

要證明

u_{n} = 2^{n} - 1 對所有整數 n \geq 3 .

令

P (n) ： u_{n} = 2^{n} - 1 .

基礎步從 $n = 3$ 開始：

u_{3} = 7 = 2^{3} - 1,

所以 $P (3)$ 成立。

歸納步也必須與這個範圍對齊：

取任意整數 $k \geq 3$ ，假設

u_{k} = 2^{k} - 1 .

由遞迴式，

\begin{aligned} u_{k + 1} & = 2 u_{k} + 1 \\ = 2 (2^{k} - 1) + 1 \\ = 2^{k + 1} - 2 + 1 \\ = 2^{k + 1} - 1 . \end{aligned}

所以 $P (k + 1)$ 成立。

因此，由第一型數學歸納法，

u_{n} = 2^{n} - 1 對所有整數 n \geq 3 成立。

回查下一項：

u_{4} = 2 \cdot 7 + 1 = 15 = 2^{4} - 1,

與公式一致。

但是，這份證明沒有證明 $n = 1$ 或 $n = 2$ 的情況。題目沒有給出那些位置的條件，我們也沒有從那些位置建立起點。

「沒有證明那些位置」不等於「公式在那些位置一定錯誤」。它的意思是：那些位置不在本題條件與這份證明所保證的範圍內。把遞迴式向前延伸到 $n = 1, 2$ ，也是另外增加條件，不能默默當成原題已知。

歸納法證明到哪裡，不只取決於公式長什麼樣，也取決於起始位置及遞迴式在哪個範圍有效。

六、看似有歸納形式，仍可能少了關鍵條件

有傳遞規則，卻沒有正確起點

假設另一個數列滿足

t_{1} = 2, t_{n + 1} = t_{n} + 2 n + 1 對每個整數 n \geq 1 .

有人想證明 $t_{n} = n^{2}$ ，並寫：

「假設 $t_{k} = k^{2}$ ，則

t_{k + 1} = t_{k} + 2 k + 1 = {(k + 1)}^{2} .

所以證明完成。」

這段代數的條件推導沒有問題，但整份證明仍不成立。因為起點是

t_{1} = 2 \neq 1^{2} .

他建立了「如果某一步符合平方公式，下一步也會符合」的傳遞，卻沒有建立第一步真的符合。

再直接算下一項，也會得到

t_{2} = 2 + 3 = 5 \neq 2^{2} .

同一條更新規則，可以配上不同的起始值。遞迴式相同，不代表起始值可以不查。

有起點，但一步跨過了某些位置

考慮命題：

P (n) ： n 是奇數 .

$P (1)$ 成立，而且如果 $k$ 是奇數， $k + 2$ 也是奇數。

但是，這不能證明每個正整數都是奇數。因為這條傳遞走的是

1 ⟶ 3 ⟶ 5 ⟶ \dots,

並沒有涵蓋 $2, 4, 6, \dots$ 。其中 $n = 2$ 就足以反駁「每個正整數都是奇數」。

本篇要求的是從 $P (k)$ 推到 $P (k + 1)$ 。只建立上述跨兩格的連接，再加上一個奇數起點，不能宣稱已覆蓋完整的相鄰整數鏈。

問題在於這份論證的覆蓋範圍不足，不是說任何跨步推理都沒有用途。

把待證目標當成已知依據

在歸納步中，先寫出

a_{k + 1} = {(k + 1)}^{2}

作為「待證目標」，並沒有錯；這能幫助你知道接下來要往哪裡推。

真正的錯誤是：把這個尚未證明的目標當作理由，拿它去證明它自己。

閱讀一份證明時，必須分清楚三種角色：題目已知的條件、暫時使用的歸納假設，以及尚待推出的下一步結論。

七、今天的連結：為什麼程式不能只看前幾次跑對？

這種「建立起點，再證明每次更新都保持性質」的思想，也出現在程式正確性的論證中。

康乃爾大學的程式設計課程，使用「迴圈不變量」描述每次檢查迴圈條件時應成立的關係，分別處理初始化、更新後維持關係，以及離開迴圈時如何得到所需結果；同時也要求檢查程序是否持續朝終止前進。康乃爾大學計算機科學系

下面是本文自設的教學程序，用來連結這個方法；不是引述該課程的程式，也不是在宣稱某個實際系統已經通過驗證。

假設輸入是一個正整數 $N$ ，執行過程中 $N$ 不變，所有運算都採精確整數運算：

令 j = 1，s = 1。

只要 j < N，就依序執行：
    s ← s + 2j + 1
    j ← j + 1

輸出 s。

箭頭 $\leftarrow$ 表示把右邊算出的結果存回左邊。兩個更新必須依序執行；計算 $s + 2 j + 1$ 時，用的是更新前的 $j$ 。

我們想證明：程序結束時，輸出的是 $N^{2}$ 。

要保持的不是數值，而是關係

考慮每次檢查「 $j < N$ 」時的關係：

s = j^{2} .

這就是本例要維持的不變量。「不變」不是說 $s$ 或 $j$ 都不變，而是說它們改變時，這個關係仍然成立。

起初，

j = 1, s = 1,

所以 $s = j^{2}$ 成立。

現在，假設某次準備執行更新時，

j = k, s = k^{2} .

第一個更新使 $s$ 變成

k^{2} + 2 k + 1 = {(k + 1)}^{2} .

第二個更新使 $j$ 變成 $k + 1$ 。

因此，兩個更新都完成後，再次有

s = j^{2} .

這與前面的歸納步使用完全相同的機制：某個整數位置的關係成立，就能傳到下一個整數位置。

也要注意：我們保證關係成立的位置，是每次檢查迴圈條件時。在第一個更新已做完、第二個更新尚未做完的中間時刻，不能直接沿用同一個敘述。

還要確認它會停，而且停在正確的位置

只有不變量，還不足以說明程序一定會結束。

本例中， $j$ 從 $1$ 開始，每次只增加 $1$ ，並且只在 $j < N$ 時更新。因為 $j$ 和 $N$ 都是整數，更新前 $j < N$ ，就表示更新後的 $j + 1$ 不會超過 $N$ 。

因此，在每次檢查條件時， $j$ 都不會越過 $N$ 。另一方面，程序離開迴圈，表示 $j < N$ 已經不成立，所以當時 $j \geq N$ 。兩項條件合在一起，才得到

j = N .

至於它是否真的能到達那裡：從 $1$ 開始，每次增加 $1$ ，經過 $N - 1$ 次更新就會到達 $N$ 。因為 $N$ 是一個固定的正整數，所需次數有限。

這時，由一直保持的 $s = j^{2}$ ，得到

s = N^{2} .

當 $N = 1$ 時，程序一次更新也不用執行，起始值 $s = 1$ 就已經是 $N^{2}$ 。這個邊界情況也被涵蓋了。

例如 $N = 3$ 時，檢查點上的 $(j, s)$ 依序是

(1, 1) ⟶ (2, 4) ⟶ (3, 9) .

這個具體執行可以用來回查，但它沒有取代前面對任意更新步驟的論證。

輸入條件也不能省略。若把不在本題範圍內的 $N = 0$ 直接送進這個程序，它會立即輸出 $1$ ，並不是 $0^{2}$ 。這不推翻剛才對正整數輸入的證明，而是提醒我們：保證成立的範圍，是證明的一部分。

這個例子不是要推薦用很多次加法取代直接平方，而是要看清楚一種判斷能力：你可以不只問「前幾次結果對不對」，還能問「每次更新為什麼都不會破壞我們要的關係」。

它的保證也有邊界。我們證明的是採用指定順序與精確整數運算的數學程序；實際程式是否忠實實現這些更新、所用數值表示是否足以容納運算結果，仍需另外檢查。

從數表中的普遍性問題，到逐步更新程序的正確性，歸納法提供的共同能力是：把「一直成立」拆成能夠檢驗的起點與傳遞條件。

面對下一個遞迴命題，你應能指出：起點在哪裡， $P (n)$ 在說什麼，由 $P (k)$ 到 $P (k + 1)$ 究竟用了哪條已知規則，以及最後涵蓋哪些整數。這些理由齊備，結論才真正超越已經算過的例子。