第8章 歸納與遞迴
8.1 歸納不是多試幾項
數學歸納法依靠自然數的歸納原理：若P(0)成立，且對每個k∈ℕ都能由P(k)推出P(k+1)，則每個n∈ℕ都有P(n)。也可以從1或其他固定整數起步，但結論範圍要跟著起點改變。
基底讓推理有地方開始；歸納步則對任意合格k證明一段可重複使用的連接。只計算前一百項並沒有提供後面的連接規則。本章使用自然數的歸納原理，不在這裡從集合論公理重新建造自然數。
8.2 例題
例題1 前n個正整數的和
對n≥1證明1+2+⋯+n=n(n+1)/2。基底n=1時，兩邊都為1。歸納步取任意k≥1，假設前k項和為k(k+1)/2。
加入第k+1項，得到k(k+1)/2+(k+1)=(k+1)(k+2)/2，正是n=k+1時的目標形式。基底與全部歸納步完成，故公式對每個正整數成立。
例題2 由遞迴規則猜到並證明公式
設a₀=1，aₙ₊₁=2aₙ+1。逐項得1、3、7、15，提示公式aₙ=2^(n+1)−1，但這串數字本身不是證明。基底n=0時右邊為1。
假設aₖ=2^(k+1)−1，代入遞迴式得到aₖ₊₁=2[2^(k+1)−1]+1=2^(k+2)−1，符合下一項公式。遞迴式保證逐項定義，歸納證明則把封閉公式連回那條規則。
例題3 強歸納證明質因數分解的存在
證明每個整數n≥2都能寫成有限個質數的乘積。採強歸納：基底2本身為質數。對任意n>2，假設2到n−1的所有整數都已有所需分解。
若n為質數，單獨的n就是分解。若n非質數且n>1，可寫n=ab，其中2≤a,b<n。強歸納假設分別給a、b有限個質數的乘積，合併兩串便得到n的分解。本題只證存在，不宣稱不同分解的唯一性已由此建立。
例題4 二階遞迴需要兩個初值
定義F₀=0、F₁=1，且Fₙ₊₂=Fₙ₊₁+Fₙ。前幾項為0、1、1、2、3、5。若另一序列G有相同兩個初值與同一遞迴規則，則兩序列逐項相同。
證明時讓歸納性質同時包含Gₖ=Fₖ與Gₖ₊₁=Fₖ₊₁。基底k=0由兩個初值給出；歸納步利用相加得到Gₖ₊₂=Fₖ₊₂，與已知的第k+1項配成下一對。只給F₀而未給F₁，不能唯一決定這個二階遞迴。
8.3 怎麼找出假的歸納步
若只證明P(k)⇒P(k+2)並給P(0)，最多沿這條鏈到達偶數位置；奇數位置還缺基底或連接。若歸納步需要k≥2，就要另外處理起點到這項限制之間的情形。
強歸納不是允許直接使用未證明的目標。它假設比目前指標小的全部情形；例題3的a、b都嚴格小於n，才有使用資格。若分解時出現a=n，就形成循環而非歸納下降。
8.4 練習
- B05-C08-Q01 用歸納證明前n個奇正整數之和為n²，n≥1。
- B05-C08-Q02 用歸納證明1+2+4+⋯+2ⁿ=2^(n+1)−1，n≥0。
- B05-C08-Q03 用歸納證明n³−n被3整除，n≥0。
- B05-C08-Q04 設b₀=2、bₙ₊₁=bₙ+3，求b₀到b₃並證明bₙ=2+3n。
- B05-C08-Q05 設c₀=0、cₙ₊₁=cₙ+n+1，求c₃並證明cₙ=n(n+1)/2。
- B05-C08-Q06 計算例題4的F₂到F₆，逐次指出用了哪兩項。
- B05-C08-Q07 若只知道P(0)與對所有k≥0有P(k)⇒P(k+2)，能否推出每個自然數的P？給出失敗模型。
- B05-C08-Q08 有人證明對n≥1的2ⁿ≥n，只做了歸納步，沒有基底。補出完整證明。
- B05-C08-Q09 只有a₀=0、aₙ₊₂=aₙ₊₁+aₙ是否決定唯一序列？給出兩組前四項。
- B05-C08-Q10 將30寫成質數乘積，並說明例題3的一般證明為何不能到「存在」就宣稱「唯一」。
8.5 完整解答
Q01
基底n=1時和為1=1²。假設前k項和為k²，下一個奇數是2k+1，所以新和為k²+(2k+1)=(k+1)²。對任意k≥1都能完成此步，故所有n≥1成立。加入的是第k+1個奇數，不能誤寫成2(k+1)+1。
Q02
n=0時左邊只有1，右邊2−1=1。若截至2ᵏ的和為2^(k+1)−1，再加2^(k+1)得到2·2^(k+1)−1=2^(k+2)−1，正是下一個指標的公式。基底與步驟的指標範圍一致。
Q03
基底n=0時為0，確實被3整除。假設k³−k=3r，其中r∈ℤ；則(k+1)³−(k+1)=(k³−k)+3k²+3k=3(r+k²+k)。新見證仍為整數，完成歸納步，所以每個n≥0皆成立。
Q04
前四項為2、5、8、11。公式在n=0給2，符合初值。若bₖ=2+3k，遞迴式給bₖ₊₁=2+3k+3=2+3(k+1)。因此公式對每個n≥0成立；前四項只是幫助觀察與核對。
Q05
c₁=1、c₂=3、c₃=6。基底n=0時公式為0。若cₖ=k(k+1)/2，則cₖ₊₁=k(k+1)/2+(k+1)=(k+1)(k+2)/2，完成歸納步。因此c₃=6也和公式一致。
Q06
F₂=F₁+F₀=1，F₃=F₂+F₁=2，F₄=F₃+F₂=3，F₅=F₄+F₃=5，F₆=F₅+F₄=8。每一步都只使用已定義的前兩項，沒有把求出的後項當成先前已知。
Q07
不能。令P(n)為「n為偶數」，則P(0)真，且偶數加2仍偶，使全部指定步驟成立；但P(1)假。這個模型同時滿足已給條件與失敗結論，因此清楚顯示奇數鏈尚未接上。
Q08
基底n=1時2≥1。對任意k≥1，假設2ᵏ≥k，則2^(k+1)=2·2ᵏ≥2k≥k+1，末步使用k≥1。因此歸納步成立，加上基底後才得所有n≥1的結論。這個歸納步沒有在k=0使用2k≥k+1。
Q09
不唯一。若另外選a₁=0，前四項為0、0、0、0；若選a₁=1，前四項為0、1、1、2。兩者都符合已給的a₀和遞迴式，卻不是同一序列，說明第二初值不可省略。
Q10
30=2·15=2·3·5，三個因子都是質數，給出一個存在見證。例題3的歸納只保證可找到一串質因數，沒有比較兩串不同分解。唯一性需要另證例如質數整除乘積時的性質，不能僅憑這一串算例宣稱所有整數的分解唯一。
8.6 本章回看
歸納確保規則沿全部自然數延續；遞迴規定如何由先前資料產生下一項。兩者常一起使用，但一個是證明原理，另一個是定義方式。