数学的帰納法: k から? k - 1 から?

• Top
• 高校理数こぼれ話
• kから? k-1から?

公開: 2022-09-06

整数を舞台とした証明の一つに、数学的帰納法があります。いわゆる「ドミノ倒し」の原理による証明です。通常は、

• 初期 (例えば n = 1) において成り立つことを示す
• n = k のときに成り立つと仮定する
• 上記仮定のもとに、 n = k+1 にて成り立つことを示す

という過程を踏まえることにより、全ての n = 1, 2, 3, ... において成り立つことが示されます。

k から? k - 1 から?

• 教科書的には n = k から始めるのが定石ですが、敢えて n = k-1 から始める方法もあります。
• 違いは、 k で始めるか k-1 で始めるかの違いですが、後者は、示された関係式が、「単純に n を k で置き換えた結果」になるため、証明結果が分かりやすくなる利点があります。

例題: n = 0, 1, 2, ... のとき、 0 + 2 + 4 + ... + 2n = n(n+1) を示す

教科書的な手法: n = k から始める

(i) n = 0 のとき

(左辺) = 0, (右辺) = 0 × (2 × 0 + 1) = 0 で、成り立つ。

(ii) n = k のとき、 0 + 2 + 4 + ... + 2k = k(k + 1) が成り立つとする。

n = k + 1 のとき、 上記両辺に 2(k+1) を足して、

0 + 2 + 4 + ... + 2k + 2(k+1) = k(k+1) + 2(k+1)
(上式の右辺) = (k+1)(k+2)

よって、n = k + 1 のときも成り立つ。

(i), (ii), より、全ての n = 0, 1, 2, .... において、 等式が成り立つ。 [終]

n = k - 1 から始める

前後は同一なので割愛します。結論が、単純に n を k に変えただけとなり、分かりやすくなっています。

(ii) n = k - 1 (k = 1, 2, 3, ...) のとき、 0 + 2 + 4 + ... + 2(k - 1) = (k - 1){(k - 1) + 1} = k(k - 1) が成り立つとする。

n = k のとき、上式の右辺と左辺に 2k を足して、

0 + 2 + 4 + ... + 2(k - 1) + 2k = k(k - 1) + 2k
(右辺) = k(k - 1 + 2) = k(k + 1)

よって、 n = k のときも、関係が成り立つ。 (後略)

漸化式が与えられた場合

• 与えられた漸化式がそのまま適用できるよう、出発点を使い分ければ良いのではと思います。
• 三項以上の漸化式でも同様で、最終的な結論が問題文の内容と一致するよう、工夫しましょう。

サイトマップ

サイトマップ(モバイル)

• 質問投稿
• 会員登録
• お問い合わせ