数学的帰納法とは

質問

数学的帰納法で、n=kのとき、成り立つとするとき、n=k+1で成り立つ。
のkは任意なのか、それとも、ある　なのか。どちらなのでしょうか。
kを任意とすると、k+1のときの証明が無意味な気がするのですが。
また、あるkとしてもすべての自然数の場合について調べ尽くしているようにおもうのですが。
　ご回答をお願いします。

回答No.5

nag0720 · ベストアンサー

＞任意のkについて、[n=kのとき成り立つ　⇒　n=k+1で成り立つ]
＞ということは、［・・・・］の中のn=kのｋは、任意でなく、ある　の感覚で処理しているというのでいいのでしょうか。

［・・・・］の中のkは、ある「任意に決めたk」なので、ある　の感覚でいいでしょうね。

＞[n=kのとき成り立つ　⇒　n=k+1で成り立つ]で、ｋをあるｋとしても、すべての自然数について成立するような気がするのですがどうでしようか。

#3でも書かれていますが、「n=kのとき成り立つ」は仮定です。
「n=kのとき成り立つ」と証明されたわけではありません。

n=1のとき成立して、「n=kのとき成り立つ　⇒　n=k+1で成り立つ」が示されたとき、初めてすべての自然数について成立することが証明されたことになります。

回答No.8

settheory

No.７です。

＞もし、ｎ＝１で成り立っていたら、ｋ＝１だから、すべての自然数について成り立つことにならないでしょうか

もちろん、最初のドミノが倒れれば全部倒れる、すべての自然数について成立するということになります。しかし、
「あるｋでP(k)が成立」∃k∈N（ P(k) ） というのは、
「成立する自然数が存在する」ということだけの主張で、成立している自然数のなかに、１があるかどうかはわかりません。ドミノでいうと、どこかでは倒れているが、それが一番目なのかどうかはわからないという状態です。
　つまり、一番目から全部倒れているケース、最初の何個かは倒れてなく途中からは全部倒れているケースの二つがあるということです。全ての自然数で成立することを言いたいのであれば、「成立している自然数のなかに１がある」、P(1)が成立することも示さなければなりません。

帰納法の枠組みを、ドミノ倒しと比較して説明してみます。

１.一番目のドミノを倒す
２.「ドミノが倒れる　ならば　次のドミノも倒れる」ように、どのドミノも配置してある

この両方があって、全部のドミノが倒れます（実際の手順は(2)が先ですが）。
　数学的帰納法も同じで、
ⅰP(1)が成立していることを、証明する
ⅱ「P(n) ⇒　P(n+1)」が、任意の自然数nについて成立することを、証明する

この両方をやることで、∀n∈N P(n)　を示したことになります。

ⅰを「あるｋでP(k)が成立」に代えたのが、冒頭の議論にあたります。
Pとして「n < n^2（nの二乗）」などを考えると、「途中から倒れている」というケースになります。（この程度を帰納法を使って考えたりは通常はしませんが・・）n=1のときは成立しませんが、n=2のときは成立しますし、ⅱの条件も満たしています。

ⅱの「任意の」を「ある」にかえてしまうと、あまり役にたちません。
（最初の質問はここのところのように思います。）
次のようなドミノを考えてみます。

１．ドミノを一個おく。（一番目のドミノ）
２．二番目のドミノを、一個目が倒れたとき倒れるようにおく。
３．三番目のドミノを、二個目のドミノが倒れても、それにぶつからないように、二個目のものから離れた位置におく。

11　　　1　　　（「1」をドミノと思ってみてください）

上のような感じにドミノを配置したということです。一番目が倒れると、二番目も倒れるので、「P(n) ⇒　P(n+1)」が成立する自然数は存在します。（n=1で成立）　しかしながら、一番目を倒しても三個目が倒れないので、全部のドミノは倒れません。「存在」ですと、上手く置いてある所がある、ということしか保証してません。他のところはでたらめという状況もでてきてしまいます。逆に言えば、「任意」のときは上のような下手くそな配置は許されないということです。

回答No.7

settheory

帰納法のもう少し一般的な形は、
∀n∈N (∀k≦n( P(k) ) ⇒　P(n+1) ) です。（Pは自然数に関する命題）
ｎ以下の全ての自然数について成立するなら（そう仮定した時に）、n+1でも成立する　ということです。このことが全てのnでいえ、かつ　P(0)が成立するとき、どの自然数でも成立するというのが、帰納法の主張です。ですからどちらかといえば「任意の」と思います。

高校の教科書などでは、「n=k」と、nをkに書き直しますが、その必然性は（数学的には）全くないです。「ｎのとき成立すると仮定し、n+1でも成立することを示す」という風にやっても何も問題ありません。（nをkに代えても問題ないです。）意味のない書き直しが理解の妨げになってると思われます。

質問にあるように、「ある」で解釈すると次のようになってしまうと思います。
∀n∈N 「P(n) ⇒　P(n+1)」
あるkがあってP(k)　

とします。このことから分かるのは、ｋ以上の自然数nについてP(n)が成立するということだけです。上の二つだけではk未満のところで成立するかどうかはいえません。

帰納法は良く、ドミノ倒しに例えられます。ドミノが倒れたとき、次のドミノも倒れるように、すべてのドミノは配置してあります。それゆえに、一番最初のドミノを倒すと、全部が綺麗に倒れるようになってます。（上手くいかないこともたまにはありますが・・）
「ｎのときは成立　ならば　n+1も成立」　というのは、
「ｎ番目のドミノが倒れる　ならば　n+1番目（つぎの）ドミノも倒れる」ように配置してある　という感じです。

補足

このことから分かるのは、ｋ以上の自然数nについてP(n)が成立するということだけです。上の二つだけではk未満のところで成立するかどうかはいえません。

もし、ｎ＝１で成り立っていたら、ｋ＝１だから、すべての自然数について成り立つことにならないでしょうか。

つまり、あるｋとしても、ドミノ倒しが成立しないだろうか　という疑問をもってしまいます。
　再度、ご回答をお願いします。

回答No.6

nag0720

＞任意のｋについて、［n=∃kについて成り立つ⇒n=k+1で成り立つ］
＞のように解釈していいのか。［　　］のなかのｋは、あるｋとして
＞考えて、［　　　　］のなかの関係が任意に成り立つとみているか？

そこに∃を付けちゃまずいでしょう。
記号を使うなら、
∀k∈Ｎ　［kで成立⇒k+1で成立］

kは[　]の外で決めたもので、[　]の中ではkはすでに決まってるのだから、「任意」でも「ある」でもないんではないでしょうか（いわば定数のようなもの）。

回答No.4

Trick--o--

さらに追記

> あるｋだから、もし、k=1だったら、自動的にｋ＝２でも成立するのでないか
これを言うためには「n=kが成立するとき、n=k+1が成立する」を証明しなければならない。

１で成立するからといって、２で成立するとは限らないので。
たとえば
k^(k+1) + k^(k+1) = (k+1)^k
という式は（a^b→aのb乗）
k=1では成り立つ
1^2 + 1^2 = 1+1 = 2 = 2^1
が、k=2では成り立たない
(2^3 + 2^3 = 8+8 = 16) ≠ (3^2 = 9)

補足

もう少しご意見を聞かせてもらいたいのですが、
任意のｋについて、［n=∃kについて成り立つ⇒n=k+1で成り立つ］
のように解釈していいのか。［　　］のなかのｋは、あるｋとして
考えて、［　　　　］のなかの関係が任意に成り立つとみているか？

回答No.3

Trick--o--

追記

「n=kのとき成立する」は、あくまでも「仮定」であり、これ自身を証明するわけではありません

例
「お父さんがお母さんより３０歳以上年上のとき、お父さんはロリコンである」
この例で、実際にお父さんがお母さんより30歳以上年上かどうかは関係ありません。もし、お父さん（略）のとき、の話をしているだけです。

帰納法での証明も同様。
もし、「n=kで成立するとしたら」の話をしています。本当にn=kで成立するかどうかは関係有りません。

回答No.2

Trick--o--

帰納法の手順
１．n=1のときに成立することを証明する
２．「n=kで成立すると仮定」したとき、n=k+1で成立することを証明する
３．k=1で成立することは１．より明らかなので、n=kで成立することがわかる
４．n=k（=1）で成立するので２．よりn=k+1(=2)で成立する
５．n=k（=2）で成立するので２．よりn=k+1(=3)で成立する
５．n=k（=3）で成立するので２．よりn=k+1(=4)で成立する
……ゆえに、全ての自然数nにおいて成立する

回答No.1

nag0720

「任意」ですが、それが掛る範囲に注意してください。

数学的帰納法は、
任意のkについて、[n=kのとき成り立つ　⇒　n=k+1で成り立つ]
であって、
任意のkについてn=kのとき成り立つ　⇒　n=k+1で成り立つ
ではありません。

お礼

述べたかったことをもう少し簡潔にいうと、
任意のkについて、[n=(あるk)のとき成り立つ　⇒　n=k+1で成り立つ]
のように、［　　　］のなかのｋは∃ｋと考えてよいかということです。

補足

任意のkについて、[n=kのとき成り立つ　⇒　n=k+1で成り立つ]
ということは、［・・・・］の中のn=kのｋは、任意でなく、ある　の感覚で処理しているというのでいいのでしょうか。

　もう一つの質問で、[n=kのとき成り立つ　⇒　n=k+1で成り立つ]で、ｋをあるｋとしても、すべての自然数について成立するような気がするのですがどうでしようか。
　あるｋだから、もし、k=1だったら、自動的にｋ＝２でも成立するのでないか、そしてｋ＝２で成立するから、ｋ＝２でも成立する。
　つまり、ｋをあるｋとしても、すべての自然数について成立しているように思うのですが、間違っているところを指摘願えればと思います。