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

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

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