この 章 で 学ぶ こと
数学的帰納法 (mathematical induction) は、 「す べ て の 自然数n に つ いて 命題P(n) が 成 り 立 つ」 こ と を 証明 す る 強力 な 方法。 漸化式 で 推測 し た 一般項 や、 不等式・整除性 の 証明 な ど、 入試頻出 の テクニック で す。
- 数学的帰納法 の 2 ステップ 構造 を 理解 す る
- 基底 (n=1) と 帰納段階 (k→k+1) の 役割 を 知 る
- 等式 の 証明 (例: ∑k の 公式)
- 不等式 の 証明 (例: 2n>n)
- 整除性 の 証明 (例: n3−n は 6 の 倍数)
ポイント: 数学的帰納法 は ドミノ理論 で イメージ。 「1 番目 を 倒 す」 + 「k番目 が 倒 れ れ ば k+1番目 も 倒 れ る」 → す べ て 倒 れ る。
1. 数学的帰納法 の 仕組み
2 ステップ の 流れ
す べ て の 自然数n で 命題P(n) が 成 り 立 つ こ と を 示 す に は、 次 の 2 つ を 証明 す れ ば よ い。
- 基底 (Step 1): P(1) が 成 り 立 つ
- 帰納段階 (Step 2): P(k) が 成 り 立 つ と 仮定 すれば P(k+1) も 成 り 立 つ
ドミノ で イメージ
| 条件 | ドミノ の 例 え |
|---|
| Step 1 | 1 番目 の ドミノ を 倒 す |
| Step 2 | k番目 が 倒 れ れ ば k+1番目 が 必 ず 倒 れ る (連鎖) |
| 結論 | す べ て の ドミノ が 倒 れ る |
大事: Step 2 で 使 う 「P(k) が 成 り 立 つ」 と い う 仮定 を 帰納法の仮定 と 呼 び ま す。 こ れ は 「証明中 に 使 う 道具」 で あ り、 証明 が 終 わ る ま で は 仮定 さ れ た 状態。
2. 等式 の 証明
例題 1: ∑k=1nk=2n(n+1) を 証明 せ よ
証明:
Step 1 (n=1): 左辺=1、 右辺=21⋅2=1。 → 成立 ✓
Step 2 (n=k で 成立 と 仮定): ∑i=1ki=2k(k+1) と 仮定。 こ の とき n=k+1 で
i=1∑k+1i=i=1∑ki+(k+1)=2k(k+1)+(k+1)
=(k+1)⋅2k+2=2(k+1)(k+2)
こ れ は n=k+1 の とき の 公式 と 一致。 → 成立 ✓
Step 1, 2 よ り、 す べ て の 自然数n で 等式 が 成 り 立 つ。 □
3. 不等式 の 証明
例題 2: n≥5 の とき 2n>n2 を 証明 せ よ
証明: n≥5 で 考 え る の で、 Step 1 は n=5 か ら ス タート。
Step 1 (n=5): 25=32>25=52。 → 成立 ✓
(参考: n=4 で は 24=16=42 で 等号 が 成立 す る た め、 厳密不等号2n>n2 は n≥5 の とき に 成立 す る。)
Step 2 (n=k で 成立 と 仮定, k≥5): 2k>k2 と 仮定。 n=k+1 で は
2k+1=2⋅2k>2k2
2k2≥(k+1)2 を 示 せ ば よ い。 2k2−(k+1)2=k2−2k−1=(k−1)2−2。 k≥5 で (k−1)2≥16>2 な の で 2k2>(k+1)2。
した がって 2k+1>(k+1)2。 → 成立 ✓
Step 1', 2 よ り n≥5 で 不等式 が 成 り 立 つ。 □
4. 整除性 の 証明
例題 3: す べ て の 自然数n で n3−n は 6 の 倍数 と 証明 せ よ
証明:
Step 1 (n=1): 13−1=0=6⋅0。 → 6 の 倍数 ✓
Step 2 (n=k で 成立 と 仮定): k3−k=6m (m は 整数) と 仮定。
(k+1)3−(k+1)=k3+3k2+3k+1−k−1=(k3−k)+3k(k+1)
=6m+3k(k+1)。 こ こ で k(k+1) は 連続 2 整数 の 積 で 必 ず 偶数 な の で 3k(k+1) は 6 の 倍数。 し た が っ て (k+1)3−(k+1) は 6 の 倍数。 → 成立 ✓
Step 1, 2 よ り す べ て の 自然数n で 6 の 倍数。 □
5. 漸化式 と 数学的帰納法
漸化式 で 推測 し た 一般項 を 証明 す る の が 標準的 な 使 い 方。
例題 4
a1=1、 an+1=2an+1 を 満 た す 数列 に つ いて、 an=2n−1 と な る こ と を 証明 せ よ。
証明:
Step 1 (n=1): a1=1=21−1 ✓
Step 2 (n=k で 成立 と 仮定): ak=2k−1 と 仮定。 漸化式 か ら
ak+1=2ak+1=2(2k−1)+1=2k+1−2+1=2k+1−1
→ n=k+1 で 成立 ✓
した が っ て an=2n−1 (n≥1)。 □
6. よ く あ る 誤り
NG パターン
| 誤 り | な ぜ ダ メ か |
|---|
| Step 1 を 飛 ば す | 1 番目 の ドミノ が 立 っ た ま ま に な る |
| 「P(k+1) が 成 り 立 つ と 仮定」 と 書 く | 結論 を 仮定 し て し ま う (循環論法) |
| Step 2 で n=k の 仮定 を 使 わ ず に 証明 | 帰納 の 連鎖 が 切 れ る (帰納法の意味なし) |
大事: 数学的帰納法 で は、 証明文中 で 「仮定」 と い う 言葉 を 必 ず 書 く こ と。 採点者 に 「仮定 を 使 い ま し た」 と 明示 す る の が マナー。
7. まとめ
| 用途 | パターン |
|---|
| 等式 (∑公式 な ど) | P(k)→P(k+1) で 1 項足 す |
| 不等式 | 仮定 か ら 評価 を 引 き 出 す |
| 整除性 | 仮定 と P(k+1)−P(k) を 利用 |
| 漸化式 の 一般項 | 漸化式 の 形 を そ の ま ま 使 う |
8. 強 い 帰納法
通常 の 帰納法 と の 違い
通常 の 帰納法 (Step 2 で 「P(k) を 仮定」) で は 力不足 な 場合、 強い帰納法 を 使 う。
| Step 2 で 仮定 す る もの | 名称 |
|---|
| P(k) だ け | 通常 の 帰納法 |
| P(1),P(2),…,P(k) す べ て | 強 い 帰納法 |
大事: ど ち ら も 「す べ て の 自然数n で P(n) が 成 り 立 つ」 と い う 結論 は 同 じ。 ど ち ら か で 証明 で き れ ば、 同 じ こ と が 言 え る。
例題 5 (フィボナッチ 数列 の 性質)
フィボナッチ 数列F1=1,F2=1,Fn+2=Fn+1+Fn に つ いて、 す べ て の 自然数n で Fn≥1 で あ る こ と を 強 い 帰納法 で 証明 せ よ。
証明:
Step 1: n=1,2 で F1=F2=1≥1 ✓
Step 2: n≤k で Fn≥1 と 仮定。 k+1≥3 な ら ば
Fk+1=Fk+Fk−1≥1+1=2≥1
→ 成立 ✓
し た が っ て す べ て の n で Fn≥1。 □
9. 帰納法 が 使え な い ケース (盲点)
「す べ て の 馬 は 同 じ 色」 と い う 古典的 ジョーク を 知 っ て い ま す か?
主張: n頭 の 馬 は ど の グループ で も 全員同 じ 色。
偽証明:
- Step 1 (n=1): 1 頭 だ け な ら 当然同 じ 色 ✓
- Step 2 (n=k で 成立 と 仮定): k+1頭 を 並 べ た と き、 前k頭 と 後k頭 は そ れ ぞ れ 全員同 じ 色 (仮定 よ り)、 重 な り が あ る か ら 全員同 じ 色。
→ 結論: 「す べ て の 馬 は 同 じ 色」 (明 ら か に 誤 り)
ど こ が 間違 い か: Step 2 は k+1≥3 の と き し か 重 な り が 発生 し な い。 k=1 → k+1=2 で は 前 1 頭 と 後 1 頭 が 重 な ら ず、 連鎖 が 切 れ る。
大事: 帰納法 で は 「Step 2 が す べ て の k で 機能 す る か」 を 厳 し く 確認 す る。 「重 な り が あ る か ら 同 じ」 と い う 議論 は、 重 な り が な い 初期段階 で 破綻 す る こ と が あ る。
次 の 章: 第 5 章 か ら 確率分布 に 入 り ま す。 数列 と は 別 の 話題 で す が、 「期待値 = ∑x⋅P」 の よ う に ∑ が 大活躍 し ま す。