計算機科学のブログ

帰納的定義と証明技法 累積帰納法 切手と郵便料金

情報系のための離散数学 (猪股 俊光 (著)、南野 謙一 (著)、共立出版)の第3章(帰納的定義と証明技法)、3.1(数学的帰納法)、3.1.4(累積帰納法)の問3.3の解答を求めてみる。

3 + 5 = 8

よって8円の郵便料金 3円と5円の切手により払える。

同様に、

3 · 3 = 9 5 · 2 = 10

なので9円、10円は払える。

n n 11

のとき、n-3円は払えるので、それに3円切手を1枚追加すればn円の郵便料金は払える。

よって帰納法により、8円以上の郵便料金は3円と5円の切手が十分な枚数あれば払うことができる。

(証明終)