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

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

数学的帰納法すうがくてききのうほう (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$ が大だい活かつ躍やくします。