倍数・整除性の帰納法
「すべての自然数 n に対して f(n) が m の倍数」を示す。
仮定 f(k) = m·M を使って f(k+1) を m の倍数で表す。
📘 例題① 5ⁿ + 3 は 4 の倍数であることを示せ。
解答：n=1：5+3=8=4·2 OK。
n=k仮定：5ᵏ+3 = 4M。n=k+1：5ᵏ⁺¹+3 = 5·5ᵏ+3 = 5(4M−3)+3 = 20M − 12 = 4(5M−3)。
ゆえに 4 の倍数。
解答：n=1：5+3=8=4·2 OK。
n=k仮定：5ᵏ+3 = 4M。n=k+1：5ᵏ⁺¹+3 = 5·5ᵏ+3 = 5(4M−3)+3 = 20M − 12 = 4(5M−3)。
ゆえに 4 の倍数。
💡 ポイント
- 仮定を「f(k) = m·M」と置いてから次へ繋ぐ
練習問題
- 3ⁿ − 1 が 2 の倍数であることを示せ。
解答・解説
- 解答：n=1：2 OK。n=k仮定 3ᵏ−1=2M。n=k+1：3ᵏ⁺¹−1=3(2M+1)−1=6M+2=2(3M+1)。