数学的帰納法による証明

　数学的帰納法を用いて、「8以上の数はすべて3の倍数と5の倍数で表現できる」というのを証明してください。
　ちなみにヒントとして与えられたのは、「5の倍数を使わない場合と、5の倍数を使う場合に分けて考える」というものなのですが、いまいち意味がわかりません・・・。
　どなたか回答よろしくお願いします。

No.1 回答者： Charlie24 回答日時： 2004/06/21 10:27

「8以上の数はすべて3の倍数と5の倍数で表現できる」というところは、

「8以上の”整数”はすべて3の倍数と5の倍数”の和”で表現できる」
ということでしょうか？

この回答へのお礼

問題文が十分ではありませんでしたね。失礼しました。
そのようにとってください。
「8以上の整数はすべての3の倍数と5の倍数の和で表現できることを証明せよ。」です。

お礼日時：2004/06/21 10:37

No.2 回答者： TK0318 回答日時： 2004/06/21 10:43

このヒントって必要なのでしょうか？

ヒントを使わずに解けますが・・・
（１１以上の数字は全部３＾Ｎ＋α、αは８か９か１０であらわされるから）

No.3 回答者： hinebot 回答日時： 2004/06/21 10:54

数学的帰納法自体は理解できていますか？

数学的帰納法のステップとしては、まず、
1)条件が最小のとき成立していることを示す。
　これは、n=8 のとき
　8=3+5 で、３の倍数と５の倍数の和になっている
　ということでOKですね。

2)まず、一般の数において成り立っていると仮定
　つまり、n=k (＞8) のとき
「3の倍数と5の倍数の和で表現できている」と仮定するわけです。
　すなわち、a≧0, b≧0 である整数a,bを使って
　k=3a+5b ---(1) と表せる
　とできます。

3) 2)を使って、2)の次の数について成り立つことを証明する
　つまり、n=k+1 のときについて証明していけばよいわけです。

　n=k+1のとき、(1)より、
　n=(3a+5b)+1 ---(2) ですね。

　ここで、「5の倍数を使わない場合と、5の倍数を使う場合に分けて考える」について考察してみましょう。
　5の倍数を使わない場合というのは、(1)で、b=0 のとき
　つまり、k=3a のときです。
　5の倍数を使う場合は、(1)でb≠0 のときです。
　あとは、それぞれについて(2)を検証しましょう。
　ここから先は自分で考えてみてください。
　ヒントは、
　5+1= 6 ⇒　３の倍数　ということですね。

この回答へのお礼

数学的帰納法自体は理解できているつもりなのですが・・・。
難しいですね～。

お礼日時：2004/06/21 19:17

No.4 回答者： hinebot 回答日時： 2004/06/21 11:03

#3です。

ヒント追加。

>　ヒントは、
>　5+1= 6 ⇒　３の倍数　ということですね。

同じことですが、これを逆にみて
6-1 = 5 ⇒ ５の倍数
ということも使います。
また、k=3a　としたとき、
8以上ということから、a≧3 となることも注意しましょう。

No.5 回答者： sakura_214 回答日時： 2004/06/21 11:41

「8以上の数」のうち，「5の倍数を使わない場合」というのは，単純にこの数自体が3の倍数になっているときと考えることができますが，これは当然3の倍数だけで表現できますね（そりゃそーだ^^）．ということで，「8以上の」そうなっていない数，つまり3で割って1余る数=3N+1(N≧3)と，3で割って2余る数=3N+2(N≧2)において，この場合は明らかに3の倍数だけでは表現できませんね．ということで，この２つの場合に対してさらに「5の倍数を使う」と表現できるそうですが（例えば31=21+10=3*7+5*2など），どう証明しますか？というのが，この問題とそのヒントの内容です．

こうやって分けると結構簡単に証明できます．3Nの場合は明らかなので証明を省略します．3N+1のケースですが，(i)N=3の場合は10=5*2で成立．(ii)N=kにおいて題意が成り立つとして，3k+1=3a+5bとおくことができるとすると，(iii)N=k+1の場合，3(k+1)+1=(3k+3)+1=(3k+1)+3=(3a+5b)+3=3(a+1)+5bよりこの場合も3と5の倍数で書くことができます．
次に3N+2のケースですが，同様に，(i)N=2の場合は8=3+5で成立．(ii)N=kにおいて題意が成り立つとして，3k+2=3a+5bとおくことができるとすると，(iii)N=k+1の場合，3(k+1)+2=(3k+3)+2=(3k+2)+3=(3a+5b)+3=3(a+1)+5bよりこの場合も3と5の倍数で書くことができます．
3N+1，3N+2のようにヒントに従って分けて考えるとどちらのケースも証明の内容はまったく同じですね．

実はこの問題はそれぞれのケースにおいて
・3N=3*N
・3N+1=3(N-2)+10=3*(N-2)+5*2
・3N+2=3(N-1)+5=3*(N-1)+5*1
と直接変形できるので，上のように数学的帰納法を使わなくても証明できます．

この回答へのお礼

ありがとうございます。ひゃー、なかなかこういうのは思いつきませんね・・・。
頭がやわらかいと思いつきませんよ・・・。
何はともあれ、詳しくありがとうございます。

お礼日時：2004/06/21 19:20

No.6 ベストアンサー 回答者： hinebot 回答日時： 2004/06/21 12:43

#3です。

#2さんへ
>１１以上の数字は全部３＾Ｎ＋α、αは８か９か１０であらわされる

このことを使うためには、これはこれで、証明を要すのでは？


#5さんへ
別に、３で割った余りで分ける必要はないと思います。
間違ってはいませんが、かえって複雑にしてませんか？


私のやり方を改めて全部書くと、こうなります。

1) n=8 の場合は、8=3+5 なので「3の倍数と5の倍数の和で表現できる」は成立。

2) n=k(≧9)のとき、
「3の倍数と5の倍数の和で表現できる」が成り立つとすると、
a≧0, b≧0 である整数a,bを使って
k=3a+5b ---(1) と表せる

3) n=k+1のとき
(i) b≧1のとき
k+1 = (3a+5b)+1 = 3a+5(b-1)+5+1 = 3a+6+5(b-1) = 3(a+2)+5(b-1)
よって「3の倍数と5の倍数の和で表現できる」は成立。
（b≧1 なので、a+2＞0, b-1≧0 となり、(1)に帰着できる）

(ii) b=0 のとき
(1)は k=3a となる。ここで、k≧9より 3a≧9　 ∴a≧3
k+1=3a+1=3(a-3)+9+1 = 3(a-3)+10 = 3(a-3)+5*2
よってこの場合も、「3の倍数と5の倍数の和で表現できる」は成立。
（a≧3なので、a-3≧0 ,2＞0 となり、(1)に帰着できる）

(i)(ii)により、b≧0であるすべてのbにおいて、n=k+1が「3の倍数と5の倍数の和で表現できる」は成立。

※ここで、「(1)に帰着できる」というのは、
「a≧0, b≧0 である整数a,bを使って　3a+5bと表せる」
が言えるという意味です。

この回答へのお礼

細かく説明ありがとうございます。
皆さんのおかげで解答することができました。
どうもありがとうございます。

お礼日時：2004/06/21 19:21