数学的帰納法

2017年1月25日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)$ が成り立つかというしくみまで理解しておかなければなりません。問題を通してしっかりと理解して下さい。しくみが理解できていれば多少の変形バージョンにも耐え得るはずです。しくみについては下の解説を見て下さい。

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

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

まだ、コメントがありません