Backward Induction

數學歸納法，Mathematical Induction，簡稱MI，是數學上最強勁的利器之一。回想起那青春的中學時光，當史丹福遇到甚麼證明不了的Pure Maths難題，都會情不自禁地試試用MI，而且成功率相當高。

MI有好幾種變化，但基本上都是兩個步驟。第一個步驟是base case，即證明某一個特定的case，最常見就是n=0或者1。第二步是induction，即證明如果在n=某個的數的情況下是正確，那在n=某個的數+1的情況下也是正確。先證明n=1的情況是對的；如果n=1的情況是對的，那n=2的情況也是對的；如果n=2的情況是對的，那n=3的情況也是對的；如果n=3的情況是對的，那n=4的情況也是對的...最後就證明到n等如每一個正整數的情況也是對的。這就像一副骨牌一樣，先推倒第一張骨牌，第一張骨牌會推倒第二張骨牌，第二張骨牌會推倒第三張骨牌...最後整副骨牌都可被推倒。

但MI有一個特殊的做法實在是非常之精彩，所以史丹福要特別寫篇文章介紹一下。這方法叫Backward Induction。那做法就是先證明n=非常大的情況是對的，然後證明如果在n=某個的數的情況下是正確，那在n=某個的數-1的情況下也是正確。這就是把骨牌調轉來推，最後把整副骨牌都推倒。

講多無謂，舉一個例子讓大家感受下這方法的精彩。大名鼎鼎的AM-GM inequality，所有讀過舊制Pure Maths的朋友都一定聽過，但大家又知不知道怎樣證明它？我們就試一次用Backward Induction。

 先來第一步，我們先證明n是非常大的情況，我們在這裡用n=2^k：

我們現在證明了所有n=2^k的情況下，P(n)都是正確的。我們把一個非常大的正整數代入k，那麼2^k也是非常大的。用骨牌的比喻的話，在一條長長的骨牌中，我們把中間的某些骨牌推到了，但基本上每一張骨牌的前面都必定有一張骨牌已被推倒（只要我們代入一個足夠大的k就可以了）。

最後，我們把骨牌向後推，證明當如果在n是某個的數的情況下是正確，那在n是某個的數-1的情況下也是正確。

 大名鼎鼎的AM-GM inequality就是這樣被證明了！這是多麼的優美！

話說在很久以前的Pure Maths syllabus中，backward induction是在課程範圍內的，以下就是1996年AL Pure Maths Paper I的其中一題題目。

可惜不知在甚麼時候，backward induction被刪走了，大家再沒機會欣賞到這麼優雅的數學了。（而現在的DSE同學就當然更加可憐了，完全沒有機會見識到真正嚴謹與優美的數學。）

其實，backward induction也很有哲學的意味的。它告訴我們，世界上不是每一件事都是向前進就可以。有時候，如果向前行做不到你想要的效果，那不妨試試向後退一步。