2-Dimensional Mathematical Induction

在我讀中學的年代，有一種證明方法叫「數學歸納法」（用「在我讀中學附加數的年代」而不是「現時的中學附加數」這一個phrase，是因為在課程不斷cut、cut、cut下，我怕連M.I.都cut了，那麼用「現時的中學附加數」在未來就變得不適用了……）。個人覺得這是一種美麗的方法。首先，它的最基本只涉及自然數。Kronecker說過：「上帝創造了自然數，其餘的一切才是人做的工作」，可以輔證一個proposition涉及自然數是最自然最美麗的事情。而最基本的由 n = k 去到 n = k+1 ，體驗了數學是由低做起，慢慢build up上去的系統的嚴謹。

最近製造一份教中四學生「證明方法」的筆記，忽發奇想，不如在筆記中說一些特別的數學歸納法形式。最自然的就是我當年讀的附加數textbook中（註1），有一種題目類似：Prove that 3ⁿ+13 * 7ⁿ+2 is divisible by 8 for all odd n.而接下來的，當然就是二維數學歸納法了。所謂二維數學歸納法，就是想證明P(m,n)對於所有正整數m,n都是正確的話，先證明P(1,n)對所有n均正確，然後假設P(k,n)正確再證明P(k+1,n)正確（註2）。

問題是，翻看純數的past paper，所有涉及二維數學歸納法的題目都涉及其他技巧，不太適合中四學生。於是便想想自己構造一條題目出來吧。苦思良久，竟然巧合地發現我最近在科大做TA的一個course功課的某道題目，竟然可以用來作二維數學歸納法的例子！

題目是這樣的：有一個 m X n 的棋盤，其中 m 和 n 均是奇數。假設左上角的格是白色的，而棋盤的格子是黑白相隔。證明當從棋盤中移走任意一個白色方格，餘下的棋盤可以用 1 x 2的長方形密鋪。

我發給學生的題解，可以看看這裏的第一頁。這是證明方法的另一種，叫構造法，在此就不多述了。而早兩日這樣無意間發現可以有另一種使用二維數學歸納法的證明，實在太開心了。

若讀者當中有中學生，可以嘗試一下寫下用二維數學歸納法的證明，享受一下另一種數學歸納法的美麗。

---

註1：我讀附加數是2001年的事，但我當時看的是一本1990年左右出版的附加數書（原因上面已經說了）。而讀純數時，老師派了一份"Past Paper結集"的筆記。我可以從筆記中看到九十年代、八十年代、甚至七十年代的past paper questions。到了後來，偶然自己在中學教奧林匹克數學，或從其他朋友聽見現時附加數沒有了甚麼甚麼甚麼（很多的甚麼），我可以說我見證著香港數學課程不斷刪減的事實。

註2：有許許多多其他的形式，這裏說一個便算了。