• 締切済み

証明を教えてください

A1,A2 ...........Amnをmn+1の実数の列として m+1の数からなる単調増加部分列 あるいはn+1からなる単調減少部分列 が存在する これを鳩ノ巣原理を用いて証明してください

みんなの回答

回答No.2

問題は正確に書きましょう。想像して補足してみます。 >A1,A2 ...........Amnをmn+1の実数の列として 「A1,A2,・・・Amn+1をmn+1個の異なる実数の列として」が正しいと想像されます。(3箇所補いました) 定義 1.部分列:先の実数列からk個の数値を選び、順番を変えずに並べたものを長さkの部分列と呼ぶとします。ただし1≦k≦mn+1 2.単調増加部分列:部分列をB1,B2,・・・,BkとしたときB1<B2<・・・<Bkなら単調増加部分列と呼ぶことにします。 3.単調減少部分列:部分列をB1,B2,・・・,BkとしたときB1>B2>・・・>Bkなら単調減少部分列と呼ぶことにします。 4.長さ1の部分列は単調増加部分列でもあり、単調減少部分列でもあるとします。 証明する定理 長さm+1の単調増加部分列あるいは長さn+1の単調減少部分列が存在する。 指針:背理法と鳩の巣原理を用います。 証明 (1)長さm+1の単調増加部分列も長さn+1の単調減少部分列も存在しないと仮定します。 (2)元の実数列に戻って、i番目の実数Aiから始まる部分列全体を考えます。 この時、これらの部分列で単調増加列になっているものの最大の長さをXiとします。 また、、これらの部分列で単調減少列になっているものの最大の長さをYiとします。 定義と(1)よりXi、Yiは必ず存在し、1≦Xi≦m,1≦Yi≦nである。 (3)(2)と同様にi≠jなるj番目の実数Ajから始まる部分列全体を考えます。 i<jのとき、Ai>AjならYi>Yj,Ai<AjならXi>Xjとなる。 i>jのとき、Ai>AjならXi<Xj,Ai<AjならYi<Yjとなる。 よって、i≠jならXi≠XjまたはYi≠Yj (4)ここで、写像φをφ(Ai)=(Xi,Yi)として定義する。(3)の結果から、Ai≠Ajならφ(Ai)≠φ(Aj)なので、写像φは単射である。 (5)一方、集合{Ai}の要素数はmn+1,1≦Xi≦m,1≦Yi≦nから{φ(Ai)}の要素数はmn以下。よって写像φは単射ではありえない。これは(4)と矛盾。 (6)この証明のなかで、仮定したのは(1)のみ。よって(1)は偽。すなわち、長さm+1の単調増加部分列あるいは長さn+1の単調減少部分列が存在する。 蛇足:鳩の巣原理は(5)です。大きい集合から小さな集合への単射は存在しない。

全文を見る
すると、全ての回答が全文表示されます。
noname#157574
noname#157574
回答No.1

鳩ノ巣原理ではなく鳩の巣原理です。 鳩ノ巣なる地名がありますが、誤字に注意しましょう。

全文を見る
すると、全ての回答が全文表示されます。

関連するQ&A

  • 鳩ノ巣原理の証明

    1 2 ・・・ mn+1を +1個の異なる実数の列とする。このとき +1個の数からなる単調増加部分列 i_(1) i( )2 ・・・ i_(m+1) (1 2 ・・・ m+1) あるいは、+1個の数からなる単調減少部分列 i_(1 ) i(_2) ・・・ i_(n+1) (1 2 ・・・ n+1) が存在する。 このことを 鳩ノ巣原理を用いて証明してください iの横についてるカッコの中は下付き文字という事です

  • 単調数列の証明問題です

    自分なりに、以下の単調数列の証明問題を解いてみました。 間違いがあれば、ご指摘いただけるとありがたいです。 よろしくお願いします。 【問題】 数列{(n-1)/(n+1)}{n=1,2,3,...}は有界な単調数列であるか? 理由とともに、単調な場合には、単調増加であるか単調減少であるか についても求めよ。 【証明】 まず、単調増加であるかについて証明する。 (n-1)/(n+1) = {(n+1)-2}/(n+1) = 1-{2/(n+1)}と変形させる。 これにより、1より小さいことがわかる。 また、2/(n+1)は単調減少であるため、-2/(n+1)は単調増加である。 よって、1-{2/(n+1)}も単調増加であることが証明される。 次に有界であるかについて証明する。 n→∞とするとき、{1-(1/n)}/{1+(1/n)}→1となる。 よって、1-(n-1)/(n+1) = 2/n+1 > 0とあらわすことができる。 ゆえに、数列{(n-1)/(n+1)}{n=1,2,3,...}は有界な単調数列である。 証明終わり。

  • 有界な単調数列の証明(再掲)

    こちらの皆様のご指導のもと、以下の単調数列の証明問題を解いてみました。 証明が変なところがあれば、ご指導よろしくお願いします。 【問題】 数列{ 1-(1/n) }/{ 1+(1/n} }[n=1,2,3,...]は 有界な単調数列であるか? 理由とともに、単調な場合には、 単調増加であるか単調減少であるかについても求めよ。 【証明】 まず、有界かどうかについて証明する。 n→∞とすると、 lim[n→∞] { 1-(1/n) }/{ 1+(1/n} } =lim[n→∞] (n-1+2-1)/(n+1) =lim[n→∞] 1-2/(n+1)=1 よって、有界。 つぎに単調増加について証明する。 (n-1)/(n+1) = (n+1-2)/(n+1) = 1-2/(n+1)と変形させることにより、 1より小さいことがわかる。 また、2/(n+1)は単減少であることより、-2/(n+1)は単調増加。 よって、1-2/(n+1)も単調増加であることが証明される。 ∴数列{ 1-(1/n) }/{ 1+(1/n} }[n=1,2,3,...]は、 有界な単調増加である。

  • 実数の連続性について

    読み物風の数学書にこう書いてありました。 「実数の二つの系列について、 a_1,a_2,a_3,,,,, b_1,b_2,b_3,,,,, において、いかなるnにおいてa_n≦b_nでかつa_nは広義単調増加でb_nは広義単調減少であり、しかも差b_n-a_nがnが大きくなるにつれて限りなく小さくなっていくならばすべてのnにたいしてa_n≦α≦b_nとなるような数αがひとつ、しかもただ一つ存在する。 これは実数全体、あるいは直線が一列にすきまなくつながっている主張する命題にほかならない。これを実数の連続性という」 でもどうしてお腑に落ちないのが、上に書いてある命題がなぜ実数が連続だということ、隙間なく詰まっていることを表しているのかがわかりません。αが存在してなくてすべてのnでずっとa_n≦b_nでも連続性を表していると思うんですが...。 よろしくお願いします。

  • 証明

    任意の自然数100個を考えるとき 必ず二つの自然数の差が99の倍数になる自然数が二つあります それを鳩ノ巣原理で証明するとなるとどうしたらいいのでしょうか?

  • 数列の証明

    大学の課題で出された数列の証明問題です。 レベルは恐らく高校くらいだと思います。 数列が苦手で、どうしてもわからないので質問します。 正の実数a、b(a>b)に対して、数列{a(n)}{b(n)}を a(0)=a、 b(0)=b a(n+1)=(a(n)+b(n))/2、 b(n+1)=√a(n)b(n) (n≧0) で定義されるものとする。この時、 1、{a(n)}が単調減少であること、{b(n)}が単調増大であることを示せ。 2、{a(n)}が単調減少かつa(n)≧b、{b(n)}が単調増大かつb(n)≦aより、{a(n)}および{b(n)}は収束する。この時、{a(n)}の極限値と{b(n)}の極限値が一致することを示せ。 解答・解説できる方、よろしくお願いいたします。

  • 下に有界な数列{an}の極限とanの関係の証明

    こんにちは。大学学部生1年です。 処理できない問題があるのでご協力いただきたく投稿しました。 なお、今考えている証明を載せておきますので、訂正などしていただけると嬉しいです。(^^; 【問】 下に有界な単調減少列{an}について、{an}が極限αを持つならばan≧αを証明せよ。 ∵)∃Mは実数,∀nは自然数;M≦anとする。   また、αが{an}の極限であることから、   ∀ε>0,∃Nは自然数,n≧N;|an-α|<εが成り立つ。―(1)   今、an<αと仮定すると、{an}は単調減少列なので、   α>an≧an+1≧an+2≧…≧Mとなる。―(2)   (1)より、an<αのとき、α-an<ε   また、(2)より、α-an<α-an+1<α-an+2<…となり、   αが極限であることに矛盾する。   よって、an≧α                  (証終) なんか変な気がするんですよね・・・ 環境依存文字が多かったため、表記が稚拙なところがあります。すみません。

  • 数列 不等式 証明

    相異なるn個の実数a1,a2,a3,・・・,anが不等式a1-a2>a2-a3>・・・>a(n-1)-an>an-a1(n≧3)をみたすならn個の実数のうちa1が最大であることを証明せよ a1-a2、a2-a3、・・・、a(n-1)-an、an-a1は単調減少数列でどれも0でなく和が0であるからa(k-1)-ak>0>ak-a(k+1)を満たす自然数kがあるらしいのですが、なぜそうなるのでしょうか? また、a2<(a1+a3)/2<max(a1,a3)とあるのですが、max(a1,a3)とはなんでしょうか?最大値ではないですよね どういうことなのか教えてください

  • 証明2

    いつもお世話になっています。今回は次の問題で質問があります。 (1+1/n)^n <= e という事実を使って次の式を求める。(<= は以下) lim (n->∞) n^n/(n!*e^n) (= Xn とする) (* は掛けるです。) この問題では(A)の数列が増加(減少)してかつ上限(下限)が存在することが証明できたらあとはsqueeze theorem を使って解けると思うんですが、肝心のその証明がうまくいきません。予想では(A)は減少数式で0.05が下限だとおもうのですが、もし合っているならどうやってそれを証明すればいいかなにかヒントをいただけないでしょうか? やはり両側に ln をとって lnXn = ln(n^n) - ln(n!) - lne^n とでもするのでしょうか? これを試してみましたがそれでも途中で詰まります。 なにかヒントをいただければ幸いです。

  • 単調増加数列でも単調減少数列助けてください泣

    単調増加数列でも単調減少数列でもなく、収束しない。さらに収束する部分列をもたない数列は存在するか? 存在した場合:数列を答え、存在しない場合:理由を述べよ。 すいません 親切な方教えてください!!