鴿巢原理 × 數學歸納法

鴿巢原理是指「若把 n 隻鴿關在 m 個籠裡（而 n > m），則至少有一個籠關著不止一隻鴿。」

要證明這個原理，王道方法是反證：如果每個籠都關著不多於一隻鴿，則鴿的總數便不多於籠的數目，即 n ≤ m。

或許有點大材小用，鴿巢原理亦可以數學歸納法證明。

設 P(m) 為「若把 n 隻鴿關在 m 個籠裡（而 n > m），則至少有一個籠關著不止一隻鴿。」。

當 m = 1，情況便是「把不止一隻鴿關在一個籠裡」，故 P(1) 為真。

設 P(k) 為真，而 k 為正整數。

當 m = k + 1，選定某籠，考慮以下兩種情況：

一．	該籠關著不止一隻鴿。
二．	該籠關著不多於一隻鴿，則其餘 k 個籠便關著至少 n – 1 隻鴿。 由於 n > m = k + 1，故 n – 1 > k。 根據 P(k)，該 k 個籠之中至少有一個籠關著不止一隻鴿。

根據數學歸納法原理，鴿巢原理成立。