数学的帰納法は間違い？

質問

数学的帰納法はn=1のとき証明して、n=kのとき成り立っていると仮定して、n=k+1のとき成り立っていることが示せればOKというものですよね。でもこれでは証明できない気がします。「n=kのとき成り立っていると仮定している」ので、そのあくまでも【仮定】しているときにn=k+1のときが成り立ってもだめなのではないでしょうか？仮定しているだけなので実際n=kのときが成り立っているとは限らないし、成り立っている保証のない条件の下ほかのもの(n=k+1のときのもの)が成り立つからといって証明していることになるのでしょうか？

以上のように考えてしまいます。上の考え方ではどこがいけないのか教えてください。

回答No.2

tatsumi01 · ベストアンサー

「n=1のとき証明」
「n=kのとき成り立っていると仮定して、n=k+1のとき成り立っている」
を証明するわけです。

したがって、k=1 とおけば
「n=1のとき証明」
「n=1のとき成り立っていると仮定して、n=2のとき成り立っている」
が証明できるので、n=2 のときが証明できます。

有限の n に対しては上記の言明を繰り返すことにより、いつかは証明できます。dandy_lion さん、どんな値でも構いませんから n を指定してみて下さい。たとえば、n=103,572,983,447,891 としましょうか。煩雑をいとわなければ証明を書くことは簡単です。

数学基礎論で無限という立場を認めない学派があり、その立場に立てば数学的帰納法は認められません。しかし、普通の立場では認めています。

回答No.3

koko_u_

だいたいこんな感じで説明されるのか？

今証明しようとしている命題を P(n) として、P(n) が成立「しない」集合 X を考える。
X は自然数の集合だから X が空集合でなければ「最小値」 n_0 ∈ X がある。
n_0 の最小性と、1 は X に含まれないから k = n_0 - 1 は自然数で X に含まれない。すなわち P(k) は成立する
(P(k) → P(k+1)) ∧ P(k) を得たので P(k+1) = P(n_0) も得られてこれは n_0 ∈ X に矛盾

結局 X = φ の可能性のみが残される

回答No.1

sleipnir8

簡単な例としてドミノの例があります。

n=kの時、成り立つと仮定するとき、n=k+1が成り立つことを証明すればよいというのが数学的帰納法の一般的な解法です。

「n=kの時、成り立つと仮定する」とはドミノを一定の距離で並べると考えてください。
「n=kが成り立つとき、n=K+1の時、成り立つことを証明する」とは一定の間隔で置いたドミノのうち、どれかひとつが倒れると次のドミノも倒れるということを確認しているのです。

このことが言えれば、「どのドミノに対してもひとつ倒れれば次のドミノが倒れる＝すべてのドミノが倒れる」という風にすべてのnに置いて成り立つことを示すことができるのです。

あとは最初の1個目が倒れることさえ分かればすべてのドミノが倒れていく（すべてのnについて成り立つ）ことが証明できます。

抽象的な内容になってしまいましたが考え方はこんな感じでいいのではないでしょうか？

お礼

皆さん本当にありがとうございます。ドミノの例で感覚をつかみ、no2さんの説明でなるほどと思いました。no3の方の数学的な説明も参考になりました