集合と数学的帰納法

１．平面上の点P(x,y)の集合A,Bを次のように定義する。
A={P(x,y)|x>0},B{P(x,y)|y≦-(x-k)^2+k かつ y≧kx-1}
Bは空集合でなく、しかも
B⊂Aであるためには、kはどんな範囲の値でなければならないか
　＝
という問題です。わかりにくいやつは⊂の下に＝がついたものです。

２．これは数学的帰納法の問題なのですが
数学的帰納法というのは学校で決まった形にあてはめるものだと
習いある程度お決まり文句がありそれはおぼえなければならないと
習いました。で、始めにn=1を代入して成り立つと証明し
次にn=kのとき成り立つと仮定してn=k+1の場合を考えるのですが
これは右辺にk+1とする式をひとつ付け加えて左辺にそれと同じものを
あてはめて解くというものだと自分では思っているのですがそれでは
解けません・・・ちょっと読解力に欠けているので
例題を出すので解き方を教えてください。
すべての自然数nに対して下の不等式が成り立つことを示せ。
1+1/2+1/3+1/4+・・・+1/n≧2n/(n+1)
という問題です。このれいだいのさっきいった
n=kを仮定してn=k+1のところを考えるところを教えてください

No.1 回答者： zzzzzz 回答日時： 2002/03/31 16:54

[問１・答１]

最初に＝が含まれる場合について一応注意しておきますが、
この集合の包含関係に関する＝は、「A=Bでもよい」という意味であって、
「Bが{(x,y)|x≧0}に含まれればよい」という意味では決してありません。
なので、例えば(0,0)がBに含まれていたとすると、もはやB⊆Aは成り立ちません。

記述の便宜上、f(x)=-(x-k)^2+k、g(x)=kx-1とします。
このような問題はy=f(x)とy=g(x)の交点を求めるところから始めることが多いですが、
この問題でそれをやってしまうとおそらく計算が複雑になりますのでやりません。
次のように考えます。定義から、
(x,y)がBに含まれる ⇔ g(x)≦y≦f(x)が成り立つ
ですから、
B⊆A ⇔ 任意の(x,y)∈Bに対して(x,y)∈A
⇔ 任意のg(x)≦y≦f(x)を満たす(x,y)に対してx>0
⇔ 任意のf(x)-g(x)≧0を満たすxに対してx>0
さらに、f(x)-g(x)が上に凸な２次式であることを考えれば、
⇔ f(x)-g(x)=0はx≦0に解を持たない
⇔ f(0)-g(0)<0かつ２次曲線の軸はxが正の領域にある
と考えられます。ここで、
f(x)-g(x) = -(x-k)^2+k - (kx-1) = -x^2+kx-k^2+k+1
であり、明らかにy=f(x)-g(x)に対応する２次曲線の軸はx=k/2ですから、先の条件はさらに
⇔ -k^2+k+1<0かつk>0
と変形できます。これを解けば
⇔ k>(1+√5)/2
が分かります。これがB⊆Aの必要十分条件です。
問題では、さらにBが空でない、という条件がありますが、これはf(x)-g(x)≧0を満たすxが存在することと同値であり、
さらに対応する曲線が上に凸な２次曲線であることから、f(x)-g(x)=0が解を持つことと同値であることが分かります。
従って判別式を使って判定すればよく、
D = k^2 - 4(k^2-k-1) = -3k^2+4k+4 = -(3k+2)(k-2) ≧ 0
が必要十分です。これは-2/3≦k≦2と同値であり、B⊆Aの条件とまとめれば、
(1+√5)/2 < k ≦ 2
が解になります。

この回答へのお礼

うーん・・・やっぱりパソコンの数式は
見づらくて理解するのが大変です・・・
もう一度考えてだめなら始業式に先生に聞こうと
思います。ありがとうございました。

お礼日時：2002/04/03 18:18

No.2 回答者： zzzzzz 回答日時： 2002/03/31 17:25

[問２・答１]

まず解答を書きますので、それを参考に考えてください。

n=1の時、式は明らかに成り立つ。
n=kの時に成立すると仮定する。つまり、
1+1/2+...+1/k ≧ 2k/(k+1)　　　---(*)
を仮定する。この時に、
1+1/2+...+1/k+1/(k+1) ≧ 2(k+1)/(k+2)
を示したい。(左辺)-(右辺)≧0を示せばよい。
(左辺)-(右辺)
= 1+1/2+...+1/k - 2k/(k+1) + 1/(k+1) + 2k/(k+1) - 2(k+1)/(k+2)
ここで、(*)より、
≧ 1/(k+1) + 2k/(k+1) - 2(k+1)/(k+2)
= ... = 1/(k+1) - 2/(k+1)(k+2)
= k/(k+1)(k+2)
≧0
よって式はn=k+1の時も成り立つ。
従って、帰納法により式は任意の自然数nで成り立つ。

おそらく、分かりにくかったのは、
１．1+...+1/nの扱い
２．右辺に現れる(n+1)の扱い
のどちらかだと思いますが、
１は(左辺) = Σ_{i=1,2,..,n} (1/i)
と考えれば、n=k+1の時には1/(k+1)までの(k+1)項を足せばいい、ということになりますし、
２は(n+1) = ((n)+1)と考えて、(n)の部分にkを代入したり、k+1を代入したりすれば良いわけです。

No.3 回答者： stomachman 回答日時： 2002/03/31 18:57

２つめの問題についてです。

数学的帰納法もいろいろな使い方ができます。この問題では
1+1/2+1/3+1/4+......+1/n≧1+1/2+......+1/(2^n) = 2-1/(2^n)
一方、
2n/(n+1) = (2(n+1)-2)/(n+1) = 2-2/(n+1)
ですから、
(2^n)≧(n+1)/2
を示せば良いですね。

　だから
(2^n)≧(n+1)
が数学的帰納法で証明できれば文句ありません。
(1) n=1のとき
2^n= 2 = n+1
これはオッケー。
(2) n>1の場合、
(2^n)≧(n+1)
だとすると
(2^(n+1)) = 2(2^n) ≧2(n+1) = 2n+2
そしてn>1より
2n+2＞n+2
ですからこれもオッケー。

以上でQ.E.D.っす。

この回答へのお礼

分数関数の要領で式を変形するところ・・・
だから空行もいれて6行目までは理解できましたが
そのあとの(2^n)≧(n+1)/2を証明するというのが
わかりません・・・たびたびで申し訳ありません・・・

お礼日時：2002/04/03 18:21

No.4 回答者： hikaru_mac 回答日時： 2002/04/02 02:30

hikaru_macです。

質問者で、これほど、数学の記号にパソコン入力に長けている人を見る事は珍しいです。びっくりです。
shu84さん、すごいです。

ところで、no1-no3の回答者が問題の答えをしっかり解説なさっているようなので私は数学的帰納法というものについての解説をしたいと思います。
そんなんしってたよ、ってことなら、そういう風に後でコメントもらえると、無反応よりうれしいです。

-数学的帰納法-
n=1のとき正しい。n=2のとき正しい。n=3のとき正しい。、、、、と順番に確かめていけば、すべての自然数について正しいと言えるのだが、
実際は、これでは有限の数までしか、正しいと言えない。
ノートの限界もあるし、鉛筆の限界もあるし。。。。

そこで、
「n=kの時に正しいならばn=k+1の時に正しい」---(ア)
と言えたら！！！？
(ア)にk=1を代入すると
「（n=1の時に正しいかどうかはわかんないけれど、）n=1の時に正しいならばn=2の時に正しい」
ということになる。これと
「n=1の時に正しい」
をあわせると、「n=1の時もn=2の時も正しい」
となる。
次にk=2を(ア)に代入してみると、
「（n=2の時に正しいかどうかはわかんないけれど、）n=2の時に正しいならばn=3の時に正しい」
ということになる。これと
「n=1の時もn=2の時も正しい」
をあわせると、「n=1、2、3の時に正しい」
となる。
そうやって、順番にやっていくと無限に続けられて、それで、nがどんな自然数でも成り立つ、、と言える。

書き方だけど、大抵はあなたのいう通り
[1]で　n=1を代入して成り立つと証明し
[2]で　n=kのとき成り立つと仮定してn=k+1の場合に成り立つ事を証明する。
そして最後に『[1]、[2]より、すべての自然数nに対して～は成り立つ』というふうに書く。

ところで、[2]の部分の解き方だけど
これはたとえば、数学1Aのはじめの方で整数の証明問題があったでしょ？
「～Ａ～のとき～Ｂ～を証明せよ」
「～Ａ～である。～Ｂ～であることを証明せよ」
みたいなの。
これの回答と同じように
「～与式にn=kを代入したもの～が成立する。この時、～与式にn=k+1を代入したもの～が成り立つ事を証明せよ」
をとけば、いいんです。
意味わかります？
この問題を考えるふうにして解けばいいんです。

*質問があれば、いつでもどうぞ。

この回答へのお礼

丁寧な回答ありがとうございます。
ほとんど知っていましたがやっぱり
初心に戻ることも大切かなーと思ったりしました。

今年（新高3）受験を控えてなるべく
あとの祭りにならないよう先駆けている
つもりではありますが、なかなかはかどりませんね。
新学期がはじまるとプレッシャーとやる気も
高まるとは思うのですが・・・
何はともあれありがとうございました。

お礼日時：2002/04/03 18:25

No.5 回答者： stomachman 回答日時： 2002/04/04 03:53

No.3のコメントに対する回答です。

No.3はちょっと端折り過ぎでした。それに誤記が幾つかありますから、もう一回初めから書き直してみます。

●問題をはっきりさせましょう。
S(n) = Σ1/k （Σはk=1,2,....,nに関する和）
と書くことにして、
任意の自然数nについて
S(n)≧2n/(n+1)
であることを証明せよ、ってのが問題でした。
　自然数に0を含むかどうかちょっと曖昧ですが、n=0の場合、S(n) = 0、2n/(n+1)=0 ですから、n=0でもS(n)≧2n/(n+1)は成り立っています。ですから、nが正の自然数である場合だけを考えれば良い。

●そこで、
T(n) = Σ1/(2^(k-1)) （Σはk=1,2,....,nに関する和）
を考えて、
(a) 任意のn≧1について、S(n)≧T(n)
(b) 任意のn≧1について、T(n)≧2n/(n+1)
の二つを証明すれば良い。
　このための補助定理として
(c) 任意のn≧1について、T(n) = 2-1/2^(n-1)
(d) 任意のn≧1について、2^(n-1)≧n
(e) 任意のn≧1について、2^n≧n+1
を用います。先にこれらの補助定理の証明をしましょう。

●(c)「任意のn≧1について、T(n) = 2-1/2^(n-1)」の証明。これはもちろん数学的帰納法で証明してもよいのですが、等比級数の公式通りってことで、省略して良いでしょう。

●(d)「任意のn≧1について、2^(n-1)≧n」の証明。これも自明と言いたいですが、数学的帰納法ででやってみましょう。
[1] n=1の場合。
2^(n-1)=1、n=1だから、2^(n-1)≧nは確かに成り立ちます。
[2] n≧2でありかつ2^((n-1)-1)≧(n-1)であると仮定して、2^(n-1)≧nを導きます。
まず仮定である
2^((n-1)-1)≧(n-1)
の両辺を２倍すると
2^(n-1)≧2n-2
です。さらに、n≧2だから
2n-2≧n
です（2n-2≧nを移項して整理してみれば自明）。ゆえに
2^(n-1)≧2n-2≧n
よって、
2^(n-1)≧n
以上で(d)の証明は終わりです。
●(e)「任意のn≧1について、2^n≧n+1」の証明。これも自明ですよね。数学的帰納法による証明は(d)と全く同じ要領ですから、お任せしましょう。
これで補助定理(c)(d)(e)の証明はおしまいです。

●では本題です。まず(a)「任意のn≧1について、S(n)≧T(n)」の証明。数学的帰納法を使います。
[1] n=1の場合。
S(n) = 1、T(n)=1だから、S(n)≧T(n)は確かに成り立ちます。
[2] n≧2でありかつS(n-1)≧T(n-1)であると仮定して、S(n)≧T(n)を導きます。
まずS(n),T(n)の定義から、
S(n) = S(n-1)+1/n
T(n) = T(n-1)+1/(2^(n-1))
です。また補助定理(d)「任意のn≧1について、2^(n-1)≧n」より、
1/n≧1/2^(n-1)
なので、仮定
S(n-1)≧T(n-1)
から
S(n) = S(n-1)+1/n ≧ T(n-1)+1/(2^(n-1)) = T(n)
となります。
以上で(a)の証明は終わりです。

●(b)「任意のn≧1について、T(n)≧2n/(n+1)」の証明には、数学的帰納法は不必要です。
n≧1とすると、補助定理(e)「任意のn≧1について、2^n≧n+1」より、
2^(n-1)≧(n+1)/2　だから
1/(2^(n-1))≦-2/(n+1)　よって
2-1/(2^(n-1))≧2-2/(n+1)
です。そして、補助定理(c)「任意のn≧1について、T(n) = 2-1/2^(n-1)」より、
T(n) = 2 - 1/(2^(n-1))≧2-2/(n+1) = (2(n+1)-2)/(n+1) = 2n/(n+1)
以上で(b)の証明は終わりです。

★ご参考までに、以上の証明の仕方をどうやって思いつくか。
・実は(a)「S(n)≧T(n)」というのがまずヒラメクんですね。これは自明です。
・すると(b)「T(n)≧2n/(n+1)」が成り立つのかもしれない。で、nに幾つか小さい数値を入れてみてチェックします。
・どうやら成り立ちそうなので、(b)だけ証明してみます。
・旨く行ったので、あとは自明である(a)(c)(d)(e)の証明を付け加えて完成。

　一番肝腎の(b)の部分には数学的帰納法は必要ありません。(a)(c)(d)(e)の部分の数学的帰納法もごく易しいものばかりです。だからこのやり方では、数学的帰納法の練習問題、という気はあんまりしないですね。

No.6 回答者： stomachman 回答日時： 2002/04/04 15:23

No.5の回答、および数学的帰納法全般に関する注釈です。

●No.5の回答では補助定理(c)(d)(e)と定理(a)を証明するのに数学的帰納法を使いました。さらに定理(b)は別に証明しました。でもこれは全部一緒くたにして、
[1]n=1のとき
(a) S(n)≧T(n)、(b)T(n)≧2n/(n+1)、(c)T(n) = 2-1/2^(n-1) 、(d)2^(n-1)≧n 、(e)2^n≧n+1 、が成り立つ。
[2]n＞1のとき、(a) S(n-1)≧T(n-1)、(b)T(n-1)≧2(n-1)/(n-1+1)、(c)T(n-1) = 2-1/2^(n-1-1) 、(d)2^(n-1-1)≧n-1 、(e)2^(n-1)≧n-1+1 、が全部成り立つと仮定して、(a) S(n)≧T(n)、(b)T(n)≧2n/(n+1)、(c)T(n) = 2-1/2^(n-1) 、(d)2^(n-1)≧n 、(e)2^n≧n+1 を証明する。

とやっても構わないのです。ですが、ややこしくなって、見通しが悪く、間違いやすい。だからNo.5では話を分けて(a)(b)(c)(d)(e)をそれぞれ証明したのです。これも一つの「テクニック」でしょう。

●数学的帰納法ってのは任意のn∈{1,2,3,....}について、ある命題P(n)が成り立つことを証明するために、
(A)
[1] P(1)を証明する。
[2] nはn＞1である自然数であり、かつ 任意のk (kは1≦k＜nである自然数)についてP(k)が成り立つと仮定して、P(n)を証明する。

という方法です。そのバリエーションとして
(B)
[1] P(1)を証明する。
[2] nはn＞1である自然数であり、かつP(n-1)が成り立つと仮定して、P(n)を証明する。

がある。(B)は「任意のk (1≦k＜n)についてP(k)である」という仮定のうち、k=n-1の場合だけしか利用しないということですね。
　ちなみに、(A)を特に「累積帰納法」と呼び、「数学的帰納法」という言葉は(B)だけの意味で使う人もいます。

また、m=n-1とおいて
(A')
[1] P(1)を証明する。
[2] mはm≧1である自然数であり、かつ 任意のk (kは1≦k≦mである自然数)についてP(k)が成り立つと仮定して、P(m+1)を証明する。
(B')
[1] P(1)を証明する。
[2] mはm≧1である自然数であり、かつP(m)が成り立つと仮定して、P(m+1)を証明する。

とやっても全く同じ事です。

●[2]の部分の証明がポイントであることは言うまでもありません。そして、ここんところは「決まったやり方」ってのはないんです。だからこそ応用が広い。

●P(n)としてどんな命題を持ってきても良い。そこで、
どんな整数hも命題Q(h):「hはh^2より大きくない」を満たす
ことを証明したければ例えば、
P(n) = Q(n-1)かつQ(1-n)
つまり
P(n):「(n-1)^2≧(n-1)かつ(1-n)^2≧(1-n)である。」
とすれば数学的帰納法が使えます。

●もっと複雑な応用もあります。例を挙げると、
二つの変数を含む命題Q(i,j)がi＞jであるようなどんな自然数の組みi,jについても成り立つ
ことを証明するために例えば、
P(n):「任意の自然数iについてQ(i+n,n)が成り立つ。」
とする、なんて場合もあります。そして
[1] n=1の場合、P(n)が成り立つことを証明する。つまり、任意の自然数iについてQ(i,1)が成り立つことを証明する。このために
　[1-1] i=1の場合、Q(i,1)が成り立つことを証明する。
　[1-2] i＞1であって、かつQ(i-1,1)が成り立つと仮定して、Q(i,1)を証明する。
[2] n＞1であって、P(n-1)が成り立つと仮定して、P(n)を証明する。このために
　[2-1] n＞1であって、かつQ(i+n-1,n-1)が成り立つと仮定して、i=1の場合、Q(i+n,n)が成り立つことを証明する。
　[2-2] n＞1であって、かつQ(i+n-1,n-1)が成り立ち、しかもi＞1であって、かつQ(i-1,1)が成り立つと仮定して、Q(i+n,n)を証明する。

という風に、数学的帰納法が二重構造で使われる場合もあります。

●実は数学的帰納法は、自然数の性質を使って証明される一つの「定理」なんです。でも「数学的帰納法が旨く行くこと」のキチンとした証明は意外に大変で、多分大学初年級でも苦労しそうなレベルです。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

数学的帰納法を使って「馬は何頭集めても全部同じ色をしている」ということを証明してみましょう。つまり
任意のn∈{1,2,3,....}について「馬をn頭集めると全部同じ色をしている」
を証明しようという訳です。

[1] n=1のとき。１頭の馬は、それ自身と同じ色をしています。だから「馬をn頭集めると全部同じ色をしている」は確かに成り立ちます。
[2] n＞1であり、かつ「馬をn-1頭集めると全部同じ色をしている」ことを仮定します。
馬をn-1頭集めた群れがあるとしますと、仮定から、これらは全部同じ色をしている。
そこで、もう1頭馬aを連れてきて、合わせて全部でn頭にします。
最後に連れてきた馬aとは違う馬bを1頭どけると、群にはn-1頭の馬がいます。「馬をn-1頭集めると全部同じ色をしている」という仮定から、これらは全部同じ色です。
さて、馬bは最初の群の他の馬と同じ色をしていたんですから、bも群れに入れてやると、合わせて全部でn頭。これらは全部同じ色です。
　以上から「馬をn頭集めると全部同じ色をしている」ことが証明できました。
？？？？？？？？？？？？？？？？？？？？？？？？？？？？

　これは昔から良く知られている誤った証明（fallacy）です。
[1]には何の誤りもありません。
[2]はn＞2ならば、全く誤りはありません。
ただn=2の時だけ、[2]はおかしな事を言っているんです。これで全ての証明が破綻してしまう。面白いでしょ。

No.7 回答者： nozomi500 回答日時： 2002/04/05 09:21

数学的帰納法のお遊びで古典的なやつ。

「頭に毛が１本だけはえている状態は、ハゲである」
「頭にｋ本の毛が生えている状態が、ハゲであるならば
ｋ本に１本の毛が加わったからといって、ハゲでなくなるわけでない」

ｎ＝1のときハゲ。
ｎ＝ｋのときハゲであると仮定したとき、
ｎ＝ｋ+1であってもハゲは成り立つ。

したがって、頭に何本の毛があっても、ハゲである。