「nを正整数とする。(2^n) + 1は15で割り切れないことを示せ。」という問題です。
解答は帰納法で解くのではなく、nを具体化していくと15で割ったあまりが3,5,9,2・・・のパターンで推移していくのを証明すればいい問題なのですが、これに対して私は帰納法と背理法をミックスして以下のように解こうと思ったのですがだめですか。
(2^n) + 1は15で割り切れると仮定し、それを帰納法で表す。
n=1のとき3となり15で割り切れない。
n=kのとき15で割り切れると仮定する。つまり
(2^k) + 1=15m
⇔2^k=15m-1・・・(1)が成り立つと仮定する。
(1)より
(2^k+1)=2(15m-1)
=15・2m - 2
となり矛盾する。よって(2^n) + 1は15で割り切れない・・・(終)
どこかおかしそうな気がするのですが、結論として帰納法は帰納法単独でしか使えないのでしょうか。この問題は帰納法単独だけでは「(2^n) + 1は15で割ると13余る数ではない」ということしか証明できないので困ります。
よろしくおねがいします。
No.1
- 回答日時:
あなたの言っていることは
「k=1のとき成り立つ
k=nのとき成り立たないとすれば
k=n+1のとき成り立つ」
と言うことであり、一方、数学的帰納法は
「k=1のとき成り立つ
k=nのとき成り立たつとすれば
k=n+1のとき成り立つ」
ということです。
従って、あなたの説が正しいと言うように直すためには
k=nのとき成り立たないとすれば
を
k=nのとき成り立つとすれば
に変えなくてはならず,
すると問題自身に逆戻りしてしまい、
論理が循環してしまいます。
ちょっと面白そうな着想ですが、無理がありますね。
good777さんありがとうございます。
>あなたの言っていることは
「k=1のとき成り立つ
k=nのとき成り立たないとすれば
k=n+1のとき成り立つ」
私は「k=1のとき成り立たない
k=nのとき成り立たないとすれば
k=n+1のとき成り立たない」
ということを示したつもりだったのですが。
No.2
- 回答日時:
解き方はあっていると思いますが。
何がおかしいと思ったのでしょうか?
>n=1のとき3となり15で割り切れない。
n=kのとき15で割り切れると仮定する。
ここでしょうかね。「n=1のとき3となり15で割り切れない。」のに「n=kのとき15で割り切れると仮定する。」としているじゃないですか。nとn+1の関係が示せても肝心のスタートであるn=1のときが示せないと帰納法になんないじゃないですか。そしてその帰納法のスイッチを入れるためにnに2,3,4,5,・・・と代入していってもどうせみんな「15で割り切れない」んだからスイッチが入らないんですよね。困りました。。。
No.3
- 回答日時:
「n=1 で偽」および
「n=k で偽 → n=k+1で偽」を両方とも真でも
「全ての自然数について偽」は真とは限りません.
命題が,とびとびのkの値で真になる可能性があるからです.
数学的帰納法を使って証明するためには,
n=1で真であり,さらに
n=kで真であることを仮定しなければなりません.
ここを忘れると,
「全ての自然数nは2で割り切れない」と仮定する.
(1) n=1の時矛盾する.
(2) n=kのとき,整数mを使って,
k=2m+1 とおくと,
k+1 = 2m+2 = 2(m+1)
よって n=k+1のとき2で割り切れることになり,
仮定と矛盾する.
(3) (1)(2)より,全ての自然数について仮定は矛盾する.←これがうそ.
という間違いを引き起こすことになります.
続く.
>「n=1 で偽」および
「n=k で偽 → n=k+1で偽」を両方とも真でも
「全ての自然数について偽」は真とは限りません.
命題が,とびとびのkの値で真になる可能性があるからです.
すいません、もうひとつわからないのですが。偽でも真でもあまり変わらないと思うのですが。
>(1) n=1の時矛盾する.
すいません、矛盾するって書かれてありますけど、これは仮定が成立しているってことですよね。
n=1のとき仮定は証明できたけど、n=k+1の段階で「全ての自然数nは2で割り切れない」という仮定が証明されて無いじゃないですか。だからこれは帰納法で仮定が証明できないことがわかっただけで帰納法自体に問題があるとは思えないのですが。
No.4ベストアンサー
- 回答日時:
質問とは関係ないんですが、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
- 回答日時:
>「数学的帰納法&背理法」ってどのようなものなのでしょうか。
フェルマーの無限降下法とか
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でだめということを示せばよいのでは?
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 『◯と●の帰納法』 2 2023/04/19 20:57
- 数学 帰納法 3 2022/06/08 22:24
- 数学 『数学的帰納法のトリセツ』 4 2022/06/06 07:34
- 数学 数学的帰納法の質問です。 n=1、k,k+1のときすべての自然数nが成り立つという証明で、なぜ、n= 7 2023/07/02 11:59
- 数学 数学的帰納法について質問があります。 8 2023/04/05 23:32
- 数学 上三角行列のn乗の証明 2 2023/07/23 21:45
- 統計学 t統計量とF統計量について 9 2023/01/05 14:23
- 数学 どうか教えてください。 4 2022/07/02 20:18
- 数学 数学的帰納法 添付の一般項を求める問題なのですが、 赤線の部分でn=k+1としています。 そしてa( 1 2022/10/22 15:29
- 数学 数学の問題についてです。 この問題は背理法による証明の問題なのですが、 写真右上の赤線「rを有理数と 2 2022/06/28 16:28
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
超越数は必ず無理数でないとい...
-
x≠1⇒xの二乗≠1の真偽
-
命題「PならばQ」でPが偽ならば...
-
高1の数学の問題です
-
数学の背理法について質問です...
-
命題を証明せよとはどういう意...
-
「逆もまた真なり」について
-
∪{An:n∈N}を求めよ。
-
【命題が偽である場合の反例の...
-
高校数学、論理
-
命題の証明で・・・
-
証明問題です
-
xy=0ならばx=0またはy=0 の対偶...
-
a,bは互いに素な正の整数とする。
-
背理法での証明について 疑問に...
-
命題の問題がわかりません・・...
-
「逆は必ずしも真ならず」の証...
-
命題の証明がわかりません
-
背理法と対偶証明の違いについて
-
数学Aの参考書に、 「対偶によ...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
数学での背理法について
-
命題「PならばQ」でPが偽ならば...
-
命題の真偽の問題で 命題〇〇に...
-
「逆もまた真なり」について
-
a>0、b>0⇔a+b>0、ab>0
-
強い仮定、弱い仮定、とは
-
n=3の倍数ならば、n=6の倍数で...
-
カントールの対角線論法につい...
-
対偶法による無理数の証明につ...
-
数学の論理学的な質問なんです...
-
数学の背理法について質問です...
-
証明問題です
-
数学で出てくる十分性と必要性...
-
命題を証明せよとはどういう意...
-
数学 x,yは実数とする。「xy+1=...
-
ドモルガンの法則、対偶、三段論法
-
有理数を文字置き→互いに素な整...
-
命題の証明で・・・
-
共分散の符号と相関係数の符号...
-
有界でないについて
おすすめ情報