2016年5月6日 星期五

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是在課程範圍內的,以下就是1996AL Pure Maths Paper I的其中一題題目。



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

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

沒有留言:

張貼留言