帰納法と背理法の注意点について

質問

「nを正整数とする。(2^n) + 1は１５で割り切れないことを示せ。」という問題です。

解答は帰納法で解くのではなく、nを具体化していくと１５で割ったあまりが3,5,9,2・・・のパターンで推移していくのを証明すればいい問題なのですが、これに対して私は帰納法と背理法をミックスして以下のように解こうと思ったのですがだめですか。

(2^n) + 1は１５で割り切れると仮定し、それを帰納法で表す。
n=1のとき3となり15で割り切れない。
n=kのとき１５で割り切れると仮定する。つまり
(2^k) + 1=15m
⇔2^k=15m-1・・・(1)が成り立つと仮定する。
(1)より
(2^k+1)=2(15m-1)
=15・2m - 2
となり矛盾する。よって(2^n) + 1は１５で割り切れない・・・(終）

どこかおかしそうな気がするのですが、結論として帰納法は帰納法単独でしか使えないのでしょうか。この問題は帰納法単独だけでは「(2^n) + 1は１５で割ると１３余る数ではない」ということしか証明できないので困ります。

よろしくおねがいします。

回答No.4

nyonta · ベストアンサー

質問とは関係ないんですが、wolvさん。
「n=1 で偽」および
「n=k で偽 → n=k+1で偽」が両方とも真なら
「全ての自然数について偽」は真ですよ。(たぶん…／汗)

但し、space-travelの証明では、
「n=k で偽 → n=k+1で偽」
がきちんと証明されてません。(というか、仮定から間違ってます。。)ちなみに、この手の問題を数学的帰納法＆背理法で解くのは非常に面倒くさいです。(不可能ではないですよ。ただ、結果的にあまりで場合分けするので、王道で解く事をお勧めします。)
ん？学問に王道無し？(笑)

お礼

＞但し、space-travelの証明では、
「n=k で偽 → n=k+1で偽」
がきちんと証明されてません。

すいません、もう一度よく考えてみるとむちゃくちゃなことがわかりました。恥ずかしいです(滝汗)

＞ちなみに、この手の問題を数学的帰納法＆背理法で解くのは非常に面倒くさいです。

えっ本当に数学的帰納法＆背理法なんてあるんですか。この問題でわかったのですが、背理法において矛盾を導き出すときにnをn=k→n=k+1のように移動させたりしたらダメ何じゃないかと思いました。同様に帰納法においてn=kのときに仮定したことと同じ結果をn=k+1でも導き出さないと意味がないのではないかと思いました。
すいません、「数学的帰納法＆背理法」ってどのようなものなのでしょうか。興味があるのでお聞かせください。併用ってできるのですか？

回答No.5

motsuan

>「数学的帰納法＆背理法」ってどのようなものなのでしょうか。
フェルマーの無限降下法とか

k=ある数では成り立たつ。
k=nで成り立たつとき
k=n+1でも成り立たつので、
ある数以上の全部の数で成り立つ。
なので
ある数で成り立つとある数以上の
全部の数で成り立ことになってまずい！
というのが数学的帰納法＋背理法なのでは？
というわけで、たとえば
めちゃくちゃな証明であれば、たとえば
ある数kで成り立つとすると、
15m = (2^k) + 1= 2^(k-4) (15+1) + 1
= 2^(k-4) + 1 = 0 (mod 15)
で、k-4も成り立つ数になるので、あとは
k=1,2,3,4でだめということを示せばよいのでは？

回答No.3

wolv

「n=1 で偽」および
「n=k で偽 → n=k+1で偽」を両方とも真でも
「全ての自然数について偽」は真とは限りません．
命題が，とびとびのkの値で真になる可能性があるからです．

数学的帰納法を使って証明するためには，
n=1で真であり，さらに
n=kで真であることを仮定しなければなりません．

ここを忘れると，

「全ての自然数nは２で割り切れない」と仮定する．
(1) n=1の時矛盾する．
(2) n=kのとき，整数mを使って，
k=2m+1 とおくと，
k+1 = 2m+2 = 2(m+1)
よって n=k+1のとき２で割り切れることになり，
仮定と矛盾する．
(3) (1)(2)より，全ての自然数について仮定は矛盾する．←これがうそ．

という間違いを引き起こすことになります．

続く．

お礼

＞「n=1 で偽」および
「n=k で偽 → n=k+1で偽」を両方とも真でも
「全ての自然数について偽」は真とは限りません．
命題が，とびとびのkの値で真になる可能性があるからです．

すいません、もうひとつわからないのですが。偽でも真でもあまり変わらないと思うのですが。

＞(1) n=1の時矛盾する．

すいません、矛盾するって書かれてありますけど、これは仮定が成立しているってことですよね。

n=1のとき仮定は証明できたけど、n=k+1の段階で「全ての自然数nは２で割り切れない」という仮定が証明されて無いじゃないですか。だからこれは帰納法で仮定が証明できないことがわかっただけで帰納法自体に問題があるとは思えないのですが。

回答No.2

po-net

解き方はあっていると思いますが。
何がおかしいと思ったのでしょうか？

お礼

＞n=1のとき3となり15で割り切れない。
n=kのとき１５で割り切れると仮定する。

ここでしょうかね。「n=1のとき3となり15で割り切れない。」のに「n=kのとき１５で割り切れると仮定する。」としているじゃないですか。nとn+1の関係が示せても肝心のスタートであるn=1のときが示せないと帰納法になんないじゃないですか。そしてその帰納法のスイッチを入れるためにnに2,3,4,5,・・・と代入していってもどうせみんな「15で割り切れない」んだからスイッチが入らないんですよね。困りました。。。

回答No.1

good777

あなたの言っていることは
「k=1のとき成り立つ
ｋ＝ｎのとき成り立たないとすれば
ｋ=n+1のとき成り立つ」

と言うことであり、一方、数学的帰納法は
「k=1のとき成り立つ
ｋ＝ｎのとき成り立たつとすれば
ｋ=n+1のとき成り立つ」

ということです。
従って、あなたの説が正しいと言うように直すためには
ｋ＝ｎのとき成り立たないとすれば
を
ｋ＝ｎのとき成り立つとすれば
に変えなくてはならず,
すると問題自身に逆戻りしてしまい、
論理が循環してしまいます。

ちょっと面白そうな着想ですが、無理がありますね。

お礼

good777さんありがとうございます。

＞あなたの言っていることは
「k=1のとき成り立つ
ｋ＝ｎのとき成り立たないとすれば
ｋ=n+1のとき成り立つ」

私は「k=1のとき成り立たない
ｋ＝ｎのとき成り立たないとすれば
ｋ=n+1のとき成り立たない」
ということを示したつもりだったのですが。