理系ハウス

数学的帰納法【証明の手順と例題】

公開日: 2026/7/11

数学的帰納法【証明の手順と例題】

数学的帰納法（すうがくてききのうほう）は、自然数に関する命題を証明するための強力な手法です。「すべての自然数 nn について～が成り立つ」という主張を、有限の手順で厳密に証明できます。

1. 数学的帰納法の考え方

数学的帰納法は、ドミノ倒しのイメージで理解すると直感的です。

  • 「最初のドミノが倒れる」＝ n=1n=1 のとき命題が成り立つ
  • 「あるドミノが倒れたら次も倒れる」＝ n=kn=k で成り立てば n=k+1n=k+1 でも成り立つ

この2つが言えれば、すべてのドミノが倒れる（すべての自然数で成立する）ことが保証されます。

2. 証明の手順

自然数 nn に関する命題 P(n)P(n) を証明するには、以下の2ステップを示します。

2.1. ステップ1（基底：base case）

n=1n = 1 のとき P(1)P(1) が成り立つことを示す。

2.2. ステップ2（帰納：inductive step）

n=kn = k（kk は任意の自然数）のとき P(k)P(k) が成り立つと仮定して、P(k+1)P(k+1) が成り立つことを示す。

この2ステップが完了したとき、「すべての自然数 nn について P(n)P(n) が成り立つ」と結論づけます。

3. 例題

3.1. 例題1：Σ公式の証明

問題： すべての自然数 nn に対して、次の等式が成り立つことを数学的帰納法で証明せよ。

1+2+3+⋯+n=n(n+1)21 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}

証明：

P(n)P(n)：「∑k=1nk=n(n+1)2\displaystyle\sum_{k=1}^{n} k = \dfrac{n(n+1)}{2}」とおく。

[ステップ1] n=1n=1 のとき

左辺 =1= 1、右辺 =1×22=1= \dfrac{1 \times 2}{2} = 1。

左辺 == 右辺 となり、P(1)P(1) は成り立つ。

[ステップ2] n=kn = k のとき P(k)P(k) が成り立つと仮定する。すなわち

1+2+⋯+k=k(k+1)2⋯(∗)1 + 2 + \cdots + k = \frac{k(k+1)}{2} \quad \cdots (*)

n=k+1n = k+1 のとき、左辺を計算する。

1+2+⋯+k+(k+1)=k(k+1)2+(k+1)（仮定 (∗) を利用）1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) \quad \text{（仮定 $(*)$ を利用）} =(k+1)(k2+1)=(k+1)⋅k+22=(k+1)(k+2)2= (k+1)\left(\frac{k}{2} + 1\right) = (k+1) \cdot \frac{k+2}{2} = \frac{(k+1)(k+2)}{2}

これは P(k+1)P(k+1) の右辺 (k+1){(k+1)+1}2=(k+1)(k+2)2\dfrac{(k+1)\{(k+1)+1\}}{2} = \dfrac{(k+1)(k+2)}{2} に等しい。

よって P(k+1)P(k+1) も成り立つ。

[結論] ステップ1・ステップ2より、すべての自然数 nn に対して P(n)P(n) が成り立つ。■\blacksquare

3.2. 例題2：整除の証明

問題： すべての自然数 nn に対して、3n−13^n - 1 は 22 で割り切れることを証明せよ。

証明：

P(n)P(n)：「3n−13^n - 1 は 22 の倍数である」とおく。

[ステップ1] n=1n=1 のとき

31−1=2=2×13^1 - 1 = 2 = 2 \times 1。

22 の倍数であるから P(1)P(1) は成り立つ。

[ステップ2] n=kn = k のとき P(k)P(k) が成り立つと仮定する。すなわち

3k−1=2m(m は整数)⋯(∗)3^k - 1 = 2m \quad (m \text{ は整数}) \quad \cdots (*)

n=k+1n = k+1 のとき

3k+1−1=3⋅3k−1=3(3k−1)+3−1=3(3k−1)+23^{k+1} - 1 = 3 \cdot 3^k - 1 = 3(3^k - 1) + 3 - 1 = 3(3^k - 1) + 2

仮定 (∗)(*) より 3k−1=2m3^k - 1 = 2m なので

3k+1−1=3⋅2m+2=2(3m+1)3^{k+1} - 1 = 3 \cdot 2m + 2 = 2(3m + 1)

3m+13m + 1 は整数だから 3k+1−13^{k+1} - 1 は 22 の倍数であり、P(k+1)P(k+1) が成り立つ。

[結論] すべての自然数 nn に対して 3n−13^n - 1 は 22 で割り切れる。■\blacksquare

3.3. 例題3：不等式の証明

問題： n≥3n \geq 3 を満たすすべての自然数 nn に対して 2n>2n+12^n > 2n + 1 が成り立つことを証明せよ。

証明：

P(n)P(n)：「2n>2n+12^n > 2n + 1」とおく。今回は n≥3n \geq 3 から始まる命題なので、ステップ1は n=3n=3 で確認します。

[ステップ1] n=3n=3 のとき

左辺 =23=8= 2^3 = 8、右辺 =2×3+1=7= 2 \times 3 + 1 = 7。

8>78 > 7 なので P(3)P(3) は成り立つ。

[ステップ2] n=kn = k（k≥3k \geq 3）のとき P(k)P(k) が成り立つと仮定する。すなわち

2k>2k+1⋯(∗)2^k > 2k + 1 \quad \cdots (*)

n=k+1n = k+1 のとき

2k+1=2⋅2k>2(2k+1)=4k+2（仮定 (∗) より）2^{k+1} = 2 \cdot 2^k > 2(2k+1) = 4k + 2 \quad \text{（仮定 $(*)$ より）}

ここで k≥3k \geq 3 より 4k+2≥144k + 2 \geq 14、一方 2(k+1)+1=2k+32(k+1) + 1 = 2k + 3 と比較すると

4k+2−(2k+3)=2k−1≥2×3−1=5>04k + 2 - (2k + 3) = 2k - 1 \geq 2 \times 3 - 1 = 5 > 0

よって 4k+2>2k+3=2(k+1)+14k + 2 > 2k + 3 = 2(k+1) + 1。

したがって 2k+1>2(k+1)+12^{k+1} > 2(k+1) + 1 が成り立ち、P(k+1)P(k+1) が成り立つ。

[結論] n≥3n \geq 3 を満たすすべての自然数 nn に対して 2n>2n+12^n > 2n + 1 が成り立つ。■\blacksquare

4. 証明を書くときのポイント

  1. 何を P(n)P(n) と置くか明記する — 証明の冒頭で命題を明確にします。
  2. ステップ1・ステップ2とラベルを付ける — 採点者にわかりやすく構造化します。
  3. 「仮定より」と明示する — 帰納法の仮定をどこで使ったか示します。
  4. 結論文を書く — 「すべての自然数 nn に対して成り立つ」と締めます。

5. よくある間違い

  • n=k+1n=k+1 の式変形で仮定を使わない → 仮定を使わずに P(k+1)P(k+1) を直接示してしまうのは証明になっていません。必ず仮定 P(k)P(k) を経由して変形します。
  • 不等式で方向を間違える → 2k+1=2⋅2k>2(2k+1)2^{k+1} = 2 \cdot 2^k > 2(2k+1) のように、仮定を代入して不等号の向きを確認します。

6. 関連記事

7. クイズ

1. 数学的帰納法でまず確認しなければならないことは何か。

  • 答えを見る正解：n=1n=1（または指定された最小値）のとき命題が成り立つことを確認する（ステップ1）。

2. 帰納のステップで「n=kn=k のとき成り立つと仮定する」とき、実際に何を示す必要があるか。

  • 答えを見る正解：n=k+1n = k+1 のとき命題が成り立つことを、n=kn=k の仮定を使いながら示す。

3. n=1n=1 のとき 4n−1=34^n - 1 = 3 である。4n−14^n - 1 が 33 の倍数であることを帰納法で証明する際、4k+1−14^{k+1} - 1 をどのように変形すると仮定が使えるか。

  • 答えを見る正解： 4k+1−1=4⋅4k−1=4(4k−1)+34^{k+1} - 1 = 4 \cdot 4^k - 1 = 4(4^k - 1) + 3 と変形する。仮定より 4k−1=3m4^k - 1 = 3m なので 4(4k−1)+3=4⋅3m+3=3(4m+1)4(4^k-1)+3 = 4 \cdot 3m + 3 = 3(4m+1) となり、33 の倍数であることが示せる。
#数学的帰納法#証明#数列#数学B