数学すうがく的てき帰納きのう法ほう

この章しょうで学まなぶこと

数学的帰納法すうがくてききのうほう (mathematical induction) は、 「すべての自し然ぜん数$n$ について命題めいだい$P\left(n\right)$ が成なり立たつ」 ことを証しょう明めい する強力きょうりょくな方法ほうほう。 漸化式ぜんかしき で推すい測そく した 一般項いっぱんこう や、 不等式ふとうしき・整せい除じょ性せいの証しょう明めい など、 入試にゅうし頻出ひんしゅつのテクニックです。

• 数学すうがく的てき帰納きのう法ほう の 2 ステップ構こう造ぞう を理り解かい する
• 基き底てい ($n=1$) と 帰納段階きのうだんかい ($k\to k+1$) の役やく割わり を知しる
• 等式とうしきの証しょう明めい (例れい: $\sum k$ の公式こうしき)
• 不等式ふとうしきの証しょう明めい (例れい: $2^n>n$)
• 整せい除じょ性せいの証しょう明めい (例れい: $n^3-n$ は 6 の倍ばい数すう)

ポイント: 数学すうがく的てき帰納きのう法ほうは ドミノ理論どみのりろん でイメージ。 「1 番ばん目めを倒たおす」 + 「$k$番ばん目めが倒たおれれば $k+1$番ばん目めも倒たおれる」 → すべて倒たおれる。

1. 数学すうがく的てき帰納きのう法ほうの仕組しくみ

2 ステップの流ながれ

すべての自し然ぜん数$n$ で命題めいだい$P\left(n\right)$ が成なり立たつことを示しめすには、 次つぎの 2 つを証しょう明めい すればよい。

1. 基底きてい (Step 1): $P\left(1\right)$ が成なり立たつ
2. 帰納段階きのうだんかい (Step 2): $P\left(k\right)$ が成なり立たつと 仮か定てい すれば $P(k+1)$ も成なり立たつ

ドミノでイメージ

条じょう件けん	ドミノの例たとえ
Step 1	1 番ばん目めのドミノ を倒たおす
Step 2	$k$番ばん目めが倒たおれれば $k+1$番ばん目めが必かならず倒たおれる (連鎖れんさ)
結けつ論ろん	すべてのドミノ が倒たおれる

大事だいじ: Step 2 で使つかう 「$P\left(k\right)$ が成なり立たつ」 という仮定かていを 帰納法の仮定きのうほうのかてい と呼よびます。 これは 「証しょう明めい中に使つかう 道どう具ぐ」 であり、 証しょう明めい が終おわるまでは仮か定てい された状じょう態たい。

2. 等式とうしきの証明しょうめい

例題れいだい 1: $\sum k=1nk=\frac{n(n+1)}{2}$ を証しょう明めい せよ

証しょう明めい:

Step 1 ($n=1$): 左さ辺へん $=1$、 右う辺へん $=\frac{1\cdot 2}{2}=1$。 → 成立せいりつ ✓

Step 2 ($n=k$ で成立せいりつと仮定かてい): $\sum i=1ki=\frac{k(k+1)}{2}$ と仮か定てい。 このとき $n=k+1$ で

$\sum i=1k+1i=\sum i=1ki+(k+1)=\frac{k(k+1)}{2}+(k+1)$ $=(k+1)\cdot \frac{k+2}{2}=\frac{(k+1)(k+2)}{2}$

これは $n=k+1$ のときの公式こうしきと一いっ致ち。 → 成立せいりつ ✓

Step 1, 2 より、 すべての自し然ぜん数$n$ で等式とうしきが成なり立たつ。 □

3. 不等式ふとうしきの証明しょうめい

例題れいだい 2: $n\ge 5$ のとき $2^n>n^2$ を証しょう明めい せよ

証しょう明めい: $n\ge 5$ で考かんがえるので、 Step 1 は $n=5$ からスタート。

Step 1 ($n=5$): $2^5=32>25=5^2$。 → 成立せいりつ ✓

(参さん考こう: $n=4$ では $2^4=16=4^2$ で等号とうごうが成立せいりつするため、 厳密みつ不ふ等とう号ごう$2^n>n^2$ は $n\ge 5$ のときに成立せいりつする。)

Step 2 ($n=k$ で成立せいりつと仮定かてい, $k\ge 5$): $2^k>k^2$ と仮か定てい。 $n=k+1$ では

$2^{k+1}=2\cdot 2^k>2k^2$

$2k^2\ge (k+1{)}^2$ を示しめせばよい。 $2k^2-(k+1{)}^2=k^2-2k-1=(k-1{)}^2-2$。 $k\ge 5$ で $(k-1{)}^2\ge 16>2$ なので $2k^2>(k+1{)}^2$。

したがって $2^{k+1}>(k+1{)}^2$。 → 成立せいりつ ✓

Step 1', 2 より $n\ge 5$ で不等式ふとうしきが成なり立たつ。 □

4. 整除せいじょ性せいの証明しょうめい

例題れいだい 3: すべての自し然ぜん数$n$ で $n^3-n$ は 6 の倍ばい数すう と証しょう明めい せよ

証しょう明めい:

Step 1 ($n=1$): $1^3-1=0=6\cdot 0$。 → 6 の倍数ばいすう ✓

Step 2 ($n=k$ で成立せいりつと仮定かてい): $k^3-k=6m$ ($m$ は整数せいすう) と仮か定てい。

$(k+1{)}^3-(k+1)=k^3+3k^2+3k+1-k-1=(k^3-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

$a_1=1$、 $a_{n+1}=2a_n+1$ を満みたす 数列すうれつ について、 $a_n=2^n-1$ となることを証しょう明めい せよ。

証しょう明めい:

Step 1 ($n=1$): $a_1=1=2^1-1$ ✓

Step 2 ($n=k$ で成立せいりつと仮定かてい): $a_k=2^k-1$ と仮か定てい。 漸うたて化か式しきから

$a_{k+1}=2a_k+1=2(2^k-1)+1=2^{k+1}-2+1=2^{k+1}-1$

→ $n=k+1$ で成立せいりつ ✓

したがって $a_n=2^n-1$ ($n\ge 1$)。 □

6. よくある誤あやまり

NG パターン

誤あやまり	なぜダメか
Step 1 を飛とばす	1 番ばん目めのドミノが立たったままになる
「$P(k+1)$ が成なり立たつと仮か定てい」 と書かく	結けつ論ろん を仮か定てい してしまう (循環論法じゅんかんろんぽう)
Step 2 で $n=k$ の仮か定てい を使つかわずに証しょう明めい	帰納きのうの連れん鎖さ が切きれる (帰納法の意味なし・)

大事だいじ: 数学すうがく的てき帰納きのう法ほうでは、 証しょう明めい文中ぶんちゅうで 「仮か定てい」 という言こと葉ば を必かならず書かく こと。 採点さいてん者しゃに 「仮か定てい を使つかいました」 と明めい示じ するのがマナー。

7. まとめ

用よう途と	パターン
等式とうしき ($\sum$公式こうしきなど)	$P\left(k\right)\to P(k+1)$ で 1 項こう足たす
不等式ふとうしき	仮か定てい から評ひょう価か を引ひき出だす
整せい除じょ性せい	仮か定てい と $P(k+1)-P\left(k\right)$ を利用りよう
漸うたて化か式しきの一般いっぱん項こう	漸うたて化か式しきの形かたちをそのまま使つかう

8. 強つよい帰納きのう法ほう

通常つうじょうの帰納きのう法ほうとの違ちがい

通つう常じょう の帰納きのう法ほう (Step 2 で 「$P\left(k\right)$ を仮か定てい」) では力ちから不ふ足そく な場ば合あい、 強い帰納法つよいきのうほう を使つかう。

Step 2 で仮か定てい するもの	名称めいしょう
$P\left(k\right)$ だけ	通つう常じょう の帰納きのう法ほう
$P\left(1\right),P\left(2\right),\dots ,P\left(k\right)$ すべて	強つよい帰納きのう法ほう

大事だいじ: どちらも 「すべての自し然ぜん数$n$ で $P\left(n\right)$ が成なり立たつ」 という結けつ論ろん は同おなじ。 どちらかで証しょう明めい できれば、 同おなじことが言いえる。

例題れいだい 5 (フィボナッチ数列すうれつの性質せいしつ)

フィボナッチ数列すうれつ$F_1=1,F_2=1,F_{n+2}=F_{n+1}+F_n$ について、 すべての自し然ぜん数$n$ で $F_n\ge 1$ であることを強つよい帰納きのう法ほうで証しょう明めい せよ。

証しょう明めい:

Step 1: $n=1,2$ で $F_1=F_2=1\ge 1$ ✓

Step 2: $n\le k$ で $F_n\ge 1$ と仮か定てい。 $k+1\ge 3$ ならば

$F_{k+1}=F_k+F_{k-1}\ge 1+1=2\ge 1$

→ 成立せいりつ ✓

したがってすべての $n$ で $F_n\ge 1$。 □

9. 帰納きのう法ほうが使つかえないケース (盲点もうてん)

「すべての馬うまは同おなじ色いろ」 という 古こ典てん的てきジョーク を知しっていますか?

主張しゅちょう: $n$頭の馬うまはどのグループでも全員ぜんいん同おなじ色いろ。

偽証明ぎしょうめい:

• Step 1 ($n=1$): 1 頭あたまだけなら当然とうぜん同おなじ色いろ ✓
• Step 2 ($n=k$ で成立せいりつと仮定かてい): $k+1$頭を並ならべたとき、 前$k$頭と後$k$頭はそれぞれ全員ぜんいん同おなじ色いろ (仮か定てい より)、 重じゅうなりがあるから全員ぜんいん同おなじ色いろ。

→ 結けつ論ろん: 「すべての馬うまは同おなじ色いろ」 (明あきらかに誤あやまり)

どこが間違まちがいか: Step 2 は $k+1\ge 3$ のときしか重かさなりが発生はっせいしない。 $k=1$ → $k+1=2$ では前まえ 1 頭あたまと後ご 1 頭あたまが重かさならず、 連れん鎖さ が切きれる。

大事だいじ: 帰納きのう法ほうでは 「Step 2 がすべての $k$ で機能きのうするか」 を厳きびしく確かく認にん する。 「重じゅうなりがあるから同おなじ」 という議ぎ論ろん は、 重じゅうなりがない初しょ期き段だん階かい で破は綻たん することがある。

次じの章しょう: 第だい 5 章しょうから 確率分布かくりつぶんぷ に入はいります。 数列すうれつとは別べつの話わ題だい ですが、 「期き待たい値 = $\sum x\cdot P$」 のように $\sum$ が大だい活かつ躍やく します。