數學歸納法

推倒第一張骨牌

高一 · N-10-6

P(1) 成立,P(k)⇒P(k+1)⟹P(n) 對所有正整數 n 成立\co{P(1)}\ \text{成立},\quad \cb{P(k)\Rightarrow P(k+1)}\quad\Longrightarrow\quad P(n)\ \text{對所有正整數}\ n\ \text{成立}

先觀察

桌上排了一長排骨牌,多到數不完。

你不可能一張一張去檢查。要確定「每一張都會倒」,最少需要知道哪幾件事?

一步一步推導

  1. 排好的骨牌 P(1),P(2),P(3),…P(1),P(2),P(3),\dots,一張代表一個 nn 的敘述。P(1), P(2), P(3), …P(1),\ P(2),\ P(3),\ \dots
  2. 第一步(基底):推倒第一張,也就是證明 P(1)P(1) 成立。P(1) 成立\co{P(1)}\ \text{成立}
  3. 第二步(遞推):證明「只要第 kk 張倒,第 k+1k+1 張就一定倒」,也就是間距夠近。注意這裡的 kk 是任意一張。P(k) ⇒ P(k+1)\cb{P(k)\ \Rightarrow\ P(k+1)}
  4. 兩件事合在一起,骨牌就會一路倒下去,沒有任何一張能倖免。P(1)⇒P(2)⇒P(3)⇒⋯P(1)\Rightarrow P(2)\Rightarrow P(3)\Rightarrow\cdots
  5. 例子:1+3+5+⋯+(2n−1)=n21+3+5+\cdots+(2n-1)=n^2。假設 k×kk\times k 的正方形已經拼好,再加上一層 2k+12k+1 塊的 L 形,就變成 (k+1)×(k+1)(k+1)\times(k+1)。拖動滑桿改變 kk。k2⏟P(k)+(2k+1)=(k+1)2\underbrace{k^2}_{P(k)}+\cb{(2k+1)}=(k+1)^2
  6. 少一件就不行:沒有推第一張,或者中間有一處間距太遠,後面的骨牌都不會倒。缺基底或缺遞推 ⇒ 不能下結論\text{缺基底或缺遞推}\ \Rightarrow\ \text{不能下結論}

課綱與應用

高一共同必修,學測數 A、數 B 都在範圍內。它把「看出規律」升級成「證明規律」,也是理解遞迴式的關鍵。

練這間小屋的 5 題