難題：要證明關於無限多樣東西的事
這門學科裡幾乎每個有趣的主張，骨子裡都是一個關於無限的主張。「字母表上的每個字串都有一個定義明確的長度。」「每個正規表示式都描述某個語言。」「機器的每次接受執行都會造訪起始狀態。」字串有無限多個、表示式有無限多個、執行也有無限多個——所以你不可能一個一個地檢查到完。你需要一種方法，用有限的論證去搞定無限多種情形，而這正是歸納法給你的東西。
先從你大概已經見過的版本開始：對計數數字 0、1、2、3 等等做的普通數學歸納法。要證明一個陳述 P(n) 對每個 n 都成立，你做兩件事。首先是基底情形：證明 P(0) 為真。接著是歸納步驟：證明只要 P(k) 為真，P(k+1) 也必然為真。這兩件事合起來就像一排骨牌——基底情形推倒第一張，歸納步驟保證每張倒下的骨牌都會撞倒下一張，於是這條無限長隊伍裡的每張骨牌都會倒下。
歸納步驟裡「P(k) 為真」這個假設有個名字：歸納假設。它感覺像作弊——你居然假設了你正想證明的那種東西——但它不是，因為你只對較小的情形 k 假設它，並用它去抵達較大的情形 k+1。骨牌從不假設自己；每一張都是確確實實被前一張撞倒的。
從往上數，到往上建
普通歸納法爬的是一架由數字組成的梯子。但我們在這裡關心的物件不是數字——它們是字串、表示式與樹，這些東西並不是任何東西在明顯數值意義上「下一個」。解決辦法是注意到這些物件都是歸納地定義出來的：它們由少數幾個起始零件，用少數幾條固定的組合規則建成，此外別無其他。Sigma（字母表）上的一個字串，要嘛是空字串 epsilon（基底情形），要嘛是一個較短的字串在尾端接上一個符號（構造規則）。每個字串都能從 epsilon 經有限多步、每步一個符號地抵達。
結構歸納法就是依照這個「建造順序」而非數線來進行的歸納法。它的口號正是結構歸納法詞條裡那幅樂高圖像：若每塊基本積木都是紅的，且每個組合動作都讓東西維持紅色，那麼你所能建出的一切都是紅的——你從不檢視每一個模型，你信任基底與步驟。基底情形對起始零件證明性質；歸納步驟假設它對較小的零件成立，並說明每一條構造規則都保持它。
一個逐步走過的範例
讓我們證明一個小而真實的事實：對 Sigma 上所有字串 x 與 y，length(xy) = length(x) + length(y)，其中 xy 是 x 與 y 的串接。這正是那種看似「顯然」、卻真的得去證明的陳述，因為長度與串接本身就是用歸納法定義出來的。我們對 y 的結構做歸納——也就是對 y 是如何從 epsilon 建起來的做歸納。
- 基底情形（y 是 epsilon）：x·epsilon 就是 x，所以 length(x·epsilon) = length(x)。而 length(x) + length(epsilon) = length(x) + 0 = length(x)。兩邊相等，所以對最小的 y 主張成立。
- 歸納假設：假設主張對某個字串 w 成立，亦即對每個 x 都有 length(xw) = length(x) + length(w)。（我們只對較短的零件 w 假設它。）
- 歸納步驟（在尾端接上一個符號 a 來建出更大的 y，所以 y = wa）：那麼 xy = x(wa) = (xw)a，而附加一個符號恰好使長度加 1。所以 length(xy) = length(xw) + 1。
- 套用歸納假設：length(xw) + 1 = (length(x) + length(w)) + 1 = length(x) + (length(w) + 1) = length(x) + length(wa) = length(x) + length(y)。對 y = wa 兩邊相等，歸納步驟完成。
因為 y 是從 epsilon 開始、每次接上一個符號建出來的，而我們涵蓋了基底（epsilon）與唯一的構造規則（接上一個符號），所以性質對每個 y 都成立——因而對所有 x 與 y 一次成立。注意這個形狀：我們證了基底、假設了較小的零件、並說明那唯一的構造規則保持等式。這就是整個樣板，而你會不斷重用它。
對樹與表示式做歸納
當物件開始分岔時，真正的威力才顯現出來。一個正規表示式由基本正規表示式（單一符號、epsilon，或空集合）經三條組合規則建成：聯集、串接，以及 Kleene 星號（寫作 L*）。一個上下文無關文法的剖析樹，則由單葉的樹，依一條樹狀規則把子樹接在新的根之下而建成。要證明關於每個這類物件的性質，現在歸納步驟對每一條組合規則各有一個情形，而你要對每個較小的部分都假設歸納假設——聯集的兩個子節點、根之下的每一棵子樹。
下面是一個這類證明的脊樑：主張「每個正規表示式都表示某個語言」。基本正規表示式顯然表示語言（單一符號表示 {那個符號}，等等）。歸納步驟有三個情形：若 r 與 s 已經表示語言，則它們的聯集、它們的串接、以及 r* 也都表示語言。涵蓋這三條規則就涵蓋了每個正規表示式，因為每一個都是從基底經這三種動作中的有限多步組裝出來的。
Grammar: S -> a S b | epsilon (this generates a^n b^n, n >= 0)
Parse tree for the string a a b b :
S
/ | \
a S b <- one use of rule S -> a S b
/ | \
a S b <- another use of S -> a S b
|
epsilon <- base rule S -> epsilon (a leaf)
Structural induction on this tree:
base case : the leaf S -> epsilon yields the empty string
build rule : if subtree under inner S yields a^k b^k,
then wrapping it as a S b yields a^(k+1) b^(k+1)
conclusion : every tree of this grammar yields some a^n b^n把這棵樹從葉子往上讀，歸納幾乎自己就寫好了。唯一的基底規則位於葉子；每一次套用構造規則 a S b，都把一個較小的 a^k b^k 包成 a^(k+1) b^(k+1)。對子樹（較小的推導）假設性質，說明包裝規則保持它，你就證明了這個文法的每棵剖析樹都產生一個對稱平衡的字串。這種「由下往上」的讀法，正是為什麼樹與結構歸納法是天造地設的一對。
它會在哪裡出錯，又會通往哪裡
兩種錯誤葬送了大多數失敗的歸納證明，而兩者都來自略過樣板的某一部分。第一，在歸納步驟中漏掉一條構造規則：若一個正規表示式有三條組合規則，你卻只檢查聯集與串接，那麼每個用到 Kleene 星號的表示式就未被證明，而你的「定理」對那些情形根本是錯的。你必須涵蓋每一條規則。第二，略過或弄錯基底情形：一個完美的歸納步驟若沒有有效的基底，什麼也證明不了——骨牌排得無懈可擊，卻沒有任何人推倒第一張。
請誠實看待歸納法給了你什麼、又沒給你什麼。它證明一個陳述對某個歸納定義之集合裡的所有物件為真——它本身並不構造任何特定物件，也不會交給你一個演算法。它也只對那些確實有基底、且只需有限多步來建造的物件有效；你無法靠歸納走完一個需要無限多步才能建成的物件。而且歸納法與反證法是不同的工具：歸納法跨越所有情形把性質往上建立，反證法則假設某主張的反面並推出不可能。兩者常被合用，但不該被混淆。
歸納法也是通往本單元接下來幾個想法的入口。鴿籠原理——馬上就要登場——是那個證明「重複必定存在」的表親，它與歸納法合起來支撐了你日後會遇到的幫浦引理。而這種「建造並檢查」推理的近親，反向運行並推到無限，就成了Cantor 對角線論證，那個顯示「某些語言無法被任何機器辨識」的工具。現在把這張不起眼的骨牌練到精熟，日後那些更花俏的證明就會讓你覺得熟悉，而非魔法。