痾 . . . 歸納法是啥？沒關係，這個先別管他，來證明些數學問題吧！
現在有個理論T，而T中有一個參數n ; 我們想證明「n可以是任何自然數」的話該怎麼做呢？
最直接明瞭的方法自然就是窮舉啦 :
證明 T(n=1) 為真
證明 T(n=2) 為真
證明 T(n=3) 為真
...
可能把這串證明寫到宇宙盡頭都寫不完(❍ᴥ❍ʋ)
但是用歸納法的話只要證明兩點就好了 :
1. T(n=1)為真
2. 對所有n>1，若T(n-1)為真，則T(n)為真
條件1跟條件2證明了「T(2)為真」，而條件2跟T(2)為真又證明了「T(3)為真」 . . . 以此類推，若以上2個條件都滿足，便能證明「n可以是任何自然數」了
這樣一套歸納法能夠套用在很多地方，只要能將公理[註1]、也就是條件一的部份確認，就能以條件二來推演出接下來的情況都能成立
上面這邊，如果一時半會沒搞懂的話，建議先弄清楚再繼續往下看喔( ^ω^)，底下還會用到
讓我們再舉個例子來看看
證明 : 對任何自然數 x 與 n，x^n-1 能被 x-1 整除
我們一樣想要把用歸納的方法套用在我們的證明上，首先是條件一 :
1. T(n=1)為真:很明顯的 x^1-1 % x-1 = 0
再來看條件二，我們希望能夠證明 :
2. 對所有n>1，當x^(n-1)-1能被x-1整除時，x^n-1就能被x-1整除
如果可以證明這點，如此一來就能像第一個範例一樣用 n=2 帶入 T(n)，得出 T(n=2) 為真、再用 n=3 帶入，得出 T(n=3) 為真 . . . 便能得證「對任何自然數 x 與 n，x^n-1 能被 x-1 整除」
因此我們要想辦法將 x^n-1 換成包含 x^(n-1)-1 的形式 (也就是要證明「x^n-1 就能被 x-1 整除」)
假設 x^(n-1)-1 可以被 x-1 整除
=> x^(n-1)-1 = (x-1)*P(x)
又 x^n-1 = x*[x^(n-1)-1]+(x-1)
= x*[(x-1)*P(x)]+(x-1)
= (x-1)*[x*P(x)+(x-1)]
得證「當 x^(n-1)-1 能被 x-1 整除時，x^n-1 就能被 x-1 整除」
看到這邊應該就能大概理解歸納法是如何運作的，簡單來說就是由一推一延續下去的一推多模型，只要公理與推演的條件達成、便能無限延續下去
當然，以上的範例是最基礎的歸納模型，除了 n 一點一點減之外，還有先推出 n=1, n=2、再分別用 n-2 推演偶數與奇數等各種不同的方法，用來證明各種條件不同的證明
[註1] 公理，在傳統邏輯中，公理是沒有經過證明，但被當作不證自明的一個命題(節錄自wiki)，而在這裡「公理」表示支撐接下來推演的基本假設，與公理的意義相近、也因為書中原文也是用 “axiom” 來代表基本假設，因此使用「公理」這個字眼
本文為 Introduction to Algorithm by Manber 的閱讀筆記、有興趣的可以自己看喔(上面的是連結)，不用任何程式基礎也能看懂，不過是全英文就是了 ( ﾟ∀ﾟ)o彡ﾟ