数学的帰納法

2017年1月30日

自然数nに関する命題P(n)の証明には数学的帰納法が有効です。数学的帰納法には様々なバリエーションがあります。難関大の受験を考えている人は少なくとも次の3つは理解しておかなければなりません。まずは最も基本的なタイプから。

(1) 1段階仮定帰納法
(ⅰ) P(1)が成り立つ
(ⅱ) P(k)~(k=1,~2,~\cdots)が成り立つと仮定してP(k+1)が成り立つ
(ⅰ), (ⅱ)が示せればすべての自然数nにおいてP(n)が成り立つ.

n \geqq 2のときという条件があるときは(ⅰ)をP(2)が成り立つとすればよい。

次に2段階仮定の帰納法です。3項間漸化式で条件が与えられる場合などに有効です。3項間漸化式では前の2項が決まって初めて次の項が決まるので、前の2項を仮定しないとどうにもなりません。

(2) 2段階仮定帰納法
(ⅰ) P(1),~P(2)が成り立つ
(ⅱ) P(k),~P(k+1)~(k=1,~2,~\cdots)が成り立つと仮定してP(k+2)が成り立つ
(ⅰ), (ⅱ)が示せればすべての自然数nにおいてP(n)が成り立つ.

最後に全段階仮定の帰納法です。各項から和を求めるような状況のとき、和はすべての項が分かっていないと求まりません。そこですべての項を仮定しないとどうにもなりません。

(3) 全段階仮定帰納法
(ⅰ) P(1)が成り立つ
(ⅱ) P(1),~P(2),~\cdots,~P(k)~(k=1,~2,~\cdots)が成り立つと仮定してP(k+1)が成り立つ
(ⅰ), (ⅱ)が示せればすべての自然数nにおいてP(n)が成り立つ.

少なくともこの3つは、(ⅰ), (ⅱ)が示せればなぜすべてのnに対してP(n)が成り立つかというしくみまで理解しておかなければなりません。問題を通してしっかりと理解して下さい。しくみが理解できていれば多少の変形バージョンにも耐え得るはずです。しくみについては下の解説を見て下さい。

数学的帰納法のしくみ→解説

その他にも、後進的帰納法というものもあります。後進的帰納法については数学的帰納法4を参照して下さい。

関連ブログはこちら
にほんブログ村 教育ブログへ にほんブログ村 受験ブログへ