Binominalkoeffizient-Ungl. < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei [mm]n,m \in \IN[/mm] mit [mm]m \neq 0[/mm] und [mm]m < n[/mm]. Zeigen Sie durch direkte Rechnung:
[mm]{{m \choose k}} < {{n \choose k} \mbox{ für } k = 1, \ldots, n; \qquad \bruch{1}{m^k}{m \choose k} < \bruch{1}{n^k}{n \choose k} \leq \bruch{1}{k!} \leq \bruch{1}{2^{k-1}} \mbox{ für } k = 2, \ldots, n[/mm] |
Ich bin mir nicht sicher, was mit "direkter Rechnung" gemeint ist, aber ich versuch's einfach mal (die zweite Ungleichung beachte ich erst einmal überhaupt nicht):
[mm]\bruch{m!}{k! * (m-k)!} < \bruch{n!}{k! * (n-k)!}[/mm]
sei k=n
[mm]\bruch{m!}{n! * (m-n)!} < \bruch{n!}{n! * \underbrace{(n-n)!}_{= 1}} = \bruch{n!}{n!} = 1[/mm]
Wenn [mm](m-n)![/mm] nun immer 1 wäre, dann wäre [mm]\bruch{m!}{n!} < 1[/mm] für alle [mm]n,m \in \IN[/mm] mit [mm]m \neq 0[/mm] und [mm]m < n[/mm] wahr.
Allerdings ist [mm](m-n)![/mm] immer negativ – und mit Fakultäten von negativen, ganzen Zahlen ist das ja so eine Sache …
Mein Beweis läuft daher ins Leere. Was mache ich da falsch?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:42 Do 18.10.2012 | | Autor: | pits |
Hi Apfelchips,
> Sei [mm]n,m \in \IN[/mm] mit [mm]m \neq 0[/mm] und [mm]m < n[/mm]. Zeigen Sie durch
> direkte Rechnung:
>
> [mm]{{m \choose k}} < {{n \choose k} \mbox{ für } k = 1, \ldots, n; \qquad \bruch{1}{m^k}{m \choose k} < \bruch{1}{n^k}{n \choose k} \leq \bruch{1}{k!} \leq \bruch{1}{2^{k-1}} \mbox{ für } k = 2, \ldots, n[/mm]
>
>
> Ich bin mir nicht sicher, was mit "direkter Rechnung"
> gemeint ist, aber ich versuch's einfach mal (die zweite
> Ungleichung beachte ich erst einmal überhaupt nicht):
genau so solltest du das machen.
> [mm]\bruch{m!}{k! * (m-k)!} < \bruch{n!}{k! * (n-k)!}[/mm]
>
> sei k=n
Das k kann verschiedene Werte annehmen und deshalb sollte man das nicht festlegen. Wichtig ist hier nur, dass [mm] $k\leq [/mm] n$.
Also "einfach" mit der Ungleichung losrechnen (z.B. erst mal auf beiden Seiten mit $k!$ multiplizieren. Ich würde dann die Terme mit k auf eine Seite bringen und die anderen auf die andere, aber da muss man dann selbst mal schauen.
Gruß
pits
|
|
|
| |
|
Hey pits,
> Das k kann verschiedene Werte annehmen und deshalb sollte
> man das nicht festlegen. Wichtig ist hier nur, dass [mm]k\leq n[/mm].
Ich dachte mir schon fast, dass das, was ich versucht habe zu zeigen, nicht allgemein genug ist.
> Also "einfach" mit der Ungleichung losrechnen (z.B. erst
> mal auf beiden Seiten mit [mm]k![/mm] multiplizieren. Ich würde
> dann die Terme mit k auf eine Seite bringen und die anderen
> auf die andere, aber da muss man dann selbst mal schauen.
Ich hab's mal gewagt und die Ungleichung (genau so) umgeformt. Die Zwischenschritte poste ich jetzt nicht (es sei denn, das Ergebnis meiner Umformungsarbeiten ist falsch):
[mm]\bruch{(n-k)!}{(m-k)!} < \bruch{n!}{m!}[/mm]
k als Subtrahend im Zähler und Nenner des linken Bruchs sorgt dafür, dass der linke Ausdruck stets kleiner ist als der rechte (da [mm]k \geq 1[/mm]).
War das alles?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:31 Do 18.10.2012 | | Autor: | pits |
> [mm]\bruch{(n-k)!}{(m-k)!} < \bruch{n!}{m!}[/mm]
>
> k als Subtrahend im Zähler und Nenner des linken Bruchs
> sorgt dafür, dass der linke Ausdruck stets kleiner ist als
> der rechte (da [mm]k \geq 1[/mm]).
>
> War das alles?
Yep. Ich würde so argumentieren, dass sowohl links als auch rechts $m-n$ Faktoren stehen, die linken sind jeweils immer kleiner als ihr gegenpaart im rechten Produkt.
Gruß
pits
|
|
|
| |
|
> Ich würde so argumentieren, dass sowohl links als
> auch rechts [mm]m-n[/mm] Faktoren stehen, die linken sind jeweils
> immer kleiner als ihr gegenpaart im rechten Produkt.
Okay, dankeschön.
Dann kümmere ich mich mal um den zweiten teil der Aufgabe.
Hier fällt mir auf, dass in dem Nenner des vorletzten Terms eine Fakultät auftaucht, im Nenner des letzten Terms eine Potenz. Die Fakultät wächst schneller als jede beliebige Potenz, das heißt der Nenner des vorletzten Termins ist immer größer als der des letzten Terms. Dadurch ist der vorletzte Term immer kleiner als der letzte Term.
Für die ersten beiden Terme kann ich leider nicht so argumentieren. Es ist offensichtlich, dass ich die aus der ersten Ungleichung (die vor dem Semikolon in der Aufgabenstellung) gezogenen Erkenntnisse hier verwenden soll – allerdings stellt sich mir die Frage, wie.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:18 Do 18.10.2012 | | Autor: | pits |
Hi Apfelchips,
> Dann kümmere ich mich mal um den zweiten teil der
> Aufgabe.
> Hier fällt mir auf, dass in dem Nenner des vorletzten
> Terms eine Fakultät auftaucht, im Nenner des letzten Terms
> eine Potenz. Die Fakultät wächst schneller als jede
> beliebige Potenz, das heißt der Nenner des vorletzten
> Termins ist immer größer als der des letzten Terms.
> Dadurch ist der vorletzte Term immer kleiner als der letzte
> Term.
So kannst du nicht argumentieren, denn das Wachsen würde dann ja nur für große Werte gelten. Ich würde die Fakultät und die Potenz wieder als Produkt auffassen und jeden Faktor vergleichen.
>
> Für die ersten beiden Terme kann ich leider nicht so
> argumentieren. Es ist offensichtlich, dass ich die aus der
> ersten Ungleichung (die vor dem Semikolon in der
> Aufgabenstellung) gezogenen Erkenntnisse hier verwenden
> soll – allerdings stellt sich mir die Frage, wie.
Ich denke nicht, dass die Erkenntnis verwendet werden soll, sondern das gleiche Verfahren. Wieder hinschreiben, durch Fakultäten ausdrücken, geschickt umformen und aufmerksam hinschauen.
Leider tippe ich gerade auf meiner Handytastatur, daher ist die Antwort etwas knapp.
Gruß pits
|
|
|
| |
|
Ich komme hier leider immer noch nicht wirklich weiter …
Zunächst einmal habe ich die Ungleichungskette wie folgt umgeschrieben:
[mm]\bruch{1}{m^k}{m \choose k} < \bruch{1}{n^k}{n \choose k} \leq \bruch{1}{k!} \leq \bruch{1}{2^{k-1}}[/mm]
[mm]\bruch{1}{m^k}\left(\bruch{m!}{k!(m-k)!}\right) < \bruch{1}{n^k}\left(\bruch{n!}{k!(n-k)!}\right) \leq \bruch{1}{k(k-1)!} \leq \bruch{1}{2^{k-1}}[/mm]
Nun schaue ich mir die letzten beiden Terme an:
[mm]\bruch{1}{k(k-1)!} \leq \bruch{1}{2^{k-1}} \qquad | * 2^{k-1}[/mm]
[mm]\bruch{2^{k-1}}{k(k-1)!} \leq 1 \qquad | * k(k-1)![/mm]
[mm]2^{k-1} \leq k(k-1)![/mm]
Weitere, sinnvolle Umformungsmöglichkeiten sehe ich hier nicht.
Nun zum zweiten und dritten Term:
[mm]\bruch{1}{n^k}\left(\bruch{n!}{k!(n-k)!}\right) \leq \bruch{1}{k(k-1)!} \qquad | * n^k[/mm]
[mm]\bruch{n!n^k}{k!(n-k)!} \leq \bruch{n^k}{k(k-1)!} \qquad | : n![/mm]
[mm]\bruch{n^k}{k(k-1)! * (n-k)!} \leq \bruch{n^k}{k(k-1)! * n(n-1)!}[/mm]
Hier ist der Zähler jeweils identisch und auch die Nenner sind ähnlich. Hier ist insbesondere im rechten Bruch ein Faktor mehr zu erkennen.
Ist dieser Wege eine sinnvolle Beweisstrategie?
|
|
|
| |
|
Hallo Apfelchips,
auch hier behandelst Du offenbar nur den Fall [mm] k\le{m}, [/mm] nicht aber [mm] m
> Ich komme hier leider immer noch nicht wirklich weiter …
>
> Zunächst einmal habe ich die Ungleichungskette wie folgt
> umgeschrieben:
>
> [mm]\bruch{1}{m^k}{m \choose k} < \bruch{1}{n^k}{n \choose k} \leq \bruch{1}{k!} \leq \bruch{1}{2^{k-1}}[/mm]
>
> [mm]\bruch{1}{m^k}\left(\bruch{m!}{k!(m-k)!}\right) < \bruch{1}{n^k}\left(\bruch{n!}{k!(n-k)!}\right) \leq \bruch{1}{k(k-1)!} \leq \bruch{1}{2^{k-1}}[/mm]
Für [mm] k\le{m} [/mm] ist das ok.
> Nun schaue ich mir die letzten beiden Terme an:
>
> [mm]\bruch{1}{k(k-1)!} \leq \bruch{1}{2^{k-1}} \qquad | * 2^{k-1}[/mm]
>
> [mm]\bruch{2^{k-1}}{k(k-1)!} \leq 1 \qquad | * k(k-1)![/mm]
>
> [mm]2^{k-1} \leq k(k-1)![/mm]
>
> Weitere, sinnvolle Umformungsmöglichkeiten sehe ich hier
> nicht.
Die Aufspaltung der Fakultät ist hier nicht sinnvoll. Rechts steht ja eigentlich k! - und das hat k Faktoren, wovon der erste die 1 ist und die übrigen (k-1) Faktoren alle [mm] \ge{2} [/mm] sind.
Den Sonderfall k=1 muss man auch noch überprüfen.
> Nun zum zweiten und dritten Term:
>
> [mm]\bruch{1}{n^k}\left(\bruch{n!}{k!(n-k)!}\right) \leq \bruch{1}{k(k-1)!} \qquad | * n^k[/mm]
>
> [mm]\bruch{n!n^k}{k!(n-k)!} \leq \bruch{n^k}{k(k-1)!} \qquad | : n![/mm]
>
> [mm]\bruch{n^k}{k(k-1)! * (n-k)!} \leq \bruch{n^k}{k(k-1)! * n(n-1)!}[/mm]
>
> Hier ist der Zähler jeweils identisch und auch die Nenner
> sind ähnlich. Hier ist insbesondere im rechten Bruch ein
> Faktor mehr zu erkennen.
Auch hier ist es eher störend, k! als k(k-1)! zu schreiben.
> Ist dieser Wege eine sinnvolle Beweisstrategie?
Ich sehe keine Strategie. Du rechnest irgendwie herum, aber ohne zu wissen, wo Du eigentlich hinwillst.
[mm] \bruch{1}{n^k}\vektor{n\\k}=\bruch{1}{n^k}*\bruch{n!}{k!(n-k)!}\le\bruch{1}{k!}\quad\big|*k!
[/mm]
[mm] \bruch{n!}{n^k}*\bruch{1}{(n-k)!}\le\bruch{n!}{n^k}\le{1}
[/mm]
Der mittlere Teil ist eine einfache Abschätzung. [mm] \tfrac{1}{(n-k)!}\le{1} [/mm] gilt hier ja ohne Ausnahme.
edit: Diese Abschätzung ist falsch und daher nutzlos. Siehe meinen folgenden Beitrag.
Jetzt kannst Du den Bruch [mm] \bruch{n!}{n^k} [/mm] wieder faktorenweise betrachten.
Grüße
reverend
|
|
|
| |
|
> > Nun zum zweiten und dritten Term:
> >
> > [mm]\bruch{1}{n^k}\left(\bruch{n!}{k!(n-k)!}\right) \leq \bruch{1}{k(k-1)!} \qquad | * n^k[/mm]
>
> >
> > [mm]\bruch{n!n^k}{k!(n-k)!} \leq \bruch{n^k}{k(k-1)!} \qquad | : n![/mm]
>
> >
> > [mm]\bruch{n^k}{k(k-1)! * (n-k)!} \leq \bruch{n^k}{k(k-1)! * n(n-1)!}[/mm]
>
> >
> > Hier ist der Zähler jeweils identisch und auch die Nenner
> > sind ähnlich. Hier ist insbesondere im rechten Bruch ein
> > Faktor mehr zu erkennen.
>
> Auch hier ist es eher störend, k! als k(k-1)! zu
> schreiben.
>
> > Ist dieser Wege eine sinnvolle Beweisstrategie?
>
> Ich sehe keine Strategie. Du rechnest irgendwie herum, aber
> ohne zu wissen, wo Du eigentlich hinwillst.
Vermutlich ist das auch wirklich mein Problem …
>
> [mm]\bruch{1}{n^k}\vektor{n\\
k}=\bruch{1}{n^k}*\bruch{n!}{k!(n-k)!}\le\bruch{1}{k!}\quad\big|*k![/mm]
>
> [mm]\bruch{n!}{n^k}*\bruch{1}{(n-k)!}\le\bruch{n!}{n^k}\le{1}[/mm]
>
> Der mittlere Teil ist eine einfache Abschätzung.
> [mm]\tfrac{1}{(n-k)!}\le{1}[/mm] gilt hier ja ohne Ausnahme.
>
> Jetzt kannst Du den Bruch [mm]\bruch{n!}{n^k}[/mm] wieder
> faktorenweise betrachten.
Gestatte mir bitte diese blöde Frage: Warum sollte ich diesen Bruch weiter betrachten wollen? Das [mm]\bruch{1}{n^k}\vektor{n\\
k}\le\bruch{1}{k!}[/mm] wurde hiermit doch schon gezeigt, oder nicht?
|
|
|
| |
|
Hallo nochmal,
nein, da ist mir ein Fehler unterlaufen - die Abschätzung ist unsinnig.
> > [mm]\bruch{1}{n^k}\vektor{n\\
k}=\bruch{1}{n^k}*\bruch{n!}{k!(n-k)!}\le\bruch{1}{k!}\quad\big|*k![/mm]
>
> >
> > [mm]\bruch{n!}{n^k}*\bruch{1}{(n-k)!}\le\bruch{n!}{n^k}\le{1}[/mm]
> >
> > Der mittlere Teil ist eine einfache Abschätzung.
> > [mm]\tfrac{1}{(n-k)!}\le{1}[/mm] gilt hier ja ohne Ausnahme.
Die Mitte streichen wir besser wieder, es gilt nämlich keineswegs [mm] n!/n^k\le{1}, [/mm] nimm z.B. mal k=1...
> > Jetzt kannst Du den Bruch [mm]\bruch{n!}{n^k}[/mm] wieder
> > faktorenweise betrachten.
>
> Gestatte mir bitte diese blöde Frage: Warum sollte ich
> diesen Bruch weiter betrachten wollen? Das
> [mm]\bruch{1}{n^k}\vektor{n\\
k}\le\bruch{1}{k!}[/mm] wurde hiermit
> doch schon gezeigt, oder nicht?
Nein, leider nicht. Aber die faktorenweise Betrachtung klappt trotzdem.
Zu zeigen ist (siehe Zwischenschritt oben)
[mm] \bruch{n!}{n^k(n-k)!}\le{1}
[/mm]
Nochmal multiplizieren...
[mm] n!\le n^k(n-k)!
[/mm]
Jetzt haben wir links n Faktoren von 1 bis n, rechts n-k Faktoren von 1 bis n-k, die also eine genau gleiche Entsprechung auf der linken Seite haben, sowie k Faktoren, die alle =n sind. Die links noch verbliebenen sind aber alle [mm] \le{n}. [/mm] Die Ungleichung ist also wahr.
Besser ist das zu sehen, wenn man die Produktschreibweise wählt. Dann lautet die Ungleichung nach dem Kürzen von (n-k)! nämlich
[mm] \produkt_{i=1}^{k}(n-i+1)\le\produkt_{i=1}^{k}n
[/mm]
...und für [mm] 1\le{i} [/mm] ist nun [mm] n-i+1\le{n}.
[/mm]
So sieht man den Vergleich der Faktoren deutlicher.
Grüße
reverend
|
|
|
| |
|
Hallo,
> Nein, leider nicht. Aber die faktorenweise Betrachtung
> klappt trotzdem.
>
> Zu zeigen ist (siehe Zwischenschritt oben)
>
> [mm]\bruch{n!}{n^k(n-k)!}\le{1}[/mm]
>
> Nochmal multiplizieren...
>
> [mm]n!\le n^k(n-k)![/mm]
>
> Jetzt haben wir links n Faktoren von 1 bis n, rechts n-k
> Faktoren von 1 bis n-k, die also eine genau gleiche
> Entsprechung auf der linken Seite haben,
Bis hierhin kann ich's nachvollziehen.
> sowie k Faktoren,
> die alle =n sind. Die links noch verbliebenen sind aber
> alle [mm]\le{n}.[/mm] Die Ungleichung ist also wahr.
Aber warum sind die k Faktoren alle gleich n?
Dann noch zum Ausstehenden Vergleich [mm]\bruch{1}{m^k} {{m \choose k}} < \bruch{1}{n^k} {{n \choose k}}[/mm]:
Lässt sich hier nach Umformung zu [mm]\bruch{m!}{n!} < \bruch{m^k(m-k)!}{n^k(n-k)!}[/mm] genauso argumentieren?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:21 So 21.10.2012 | | Autor: | pits |
Hallo apfelchips
> > [mm]n!\le n^k(n-k)![/mm]
> >
> > Jetzt haben wir links n Faktoren von 1 bis n, rechts n-k
> > Faktoren von 1 bis n-k, die also eine genau gleiche
> > Entsprechung auf der linken Seite haben,
>
> Bis hierhin kann ich's nachvollziehen.
>
>
> > sowie k Faktoren,
> > die alle =n sind. Die links noch verbliebenen sind aber
> > alle [mm]\le{n}.[/mm] Die Ungleichung ist also wahr.
>
> Aber warum sind die k Faktoren alle gleich n?
Schreib dir die Faktoren alle mal hin für z.B. n=8 und k=3, dann sieht man wo die k (bzw 3) Faktoren sind, die alle gleich n (8) sind und es hilft beim verstehen.
> Dann noch zum Ausstehenden Vergleich [mm]\bruch{1}{m^k} {{m \choose k}} < \bruch{1}{n^k} {{n \choose k}}[/mm]:
>
> Lässt sich hier nach Umformung zu [mm]\bruch{m!}{n!} < \bruch{m^k(m-k)!}{n^k(n-k)!}[/mm]
> genauso argumentieren?
Man kann genau so argumentieren, ich würde aber die beiden Fakultäten mit $m$ auf eine Seite schreiben und die beiden mit $n$ auf die andere Seite, denn [mm] $\frac{m!}{(m-k)!}$ [/mm] bedeutet ja dass von dem m Faktoren (aus $m!$) die letzten m-k Faktoren "abgeschnitten" werden.
Gruß
pits
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:06 So 21.10.2012 | | Autor: | Apfelchips |
> > > sowie k Faktoren,
> > > die alle =n sind. Die links noch verbliebenen sind aber
> > > alle [mm]\le{n}.[/mm] Die Ungleichung ist also wahr.
> >
> > Aber warum sind die k Faktoren alle gleich n?
>
> Schreib dir die Faktoren alle mal hin für z.B. n=8 und
> k=3, dann sieht man wo die k (bzw 3) Faktoren sind, die
> alle gleich n (8) sind und es hilft beim verstehen.
Danke, jetzt kann ich auch das nachvollziehen: Bei [mm]n^k[/mm] taucht der Faktor n genau k mal auf (im Beispiel eben [mm]1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 \leq (8 * 8 * 8) * (1 * 2 * 3 * 4 * 5)[/mm]).
> Man kann genau so argumentieren, ich würde aber die beiden
> Fakultäten mit [mm]m[/mm] auf eine Seite schreiben und die beiden
> mit [mm]n[/mm] auf die andere Seite, denn [mm]\frac{m!}{(m-k)!}[/mm] bedeutet
> ja dass von dem m Faktoren (aus [mm]m![/mm]) die letzten m-k
> Faktoren "abgeschnitten" werden.
Ich verstehe. Also:
[mm]\bruch{m!}{m^k(m-k)!} < \bruch{n!}{n^k(n-k)!}[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:12 So 21.10.2012 | | Autor: | pits |
>
> Danke, jetzt kann ich auch das nachvollziehen: Bei [mm]n^k[/mm]
> taucht der Faktor n genau k mal auf (im Beispiel eben [mm]1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 \leq (8 * 8 * 8) * (1 * 2 * 3 * 4 * 5)[/mm]).
genau so! cool
> > Man kann genau so argumentieren, ich würde aber die beiden
> > Fakultäten mit [mm]m[/mm] auf eine Seite schreiben und die beiden
> > mit [mm]n[/mm] auf die andere Seite, denn [mm]\frac{m!}{(m-k)!}[/mm] bedeutet
> > ja dass von dem m Faktoren (aus [mm]m![/mm]) die letzten m-k
> > Faktoren "abgeschnitten" werden.
>
> Ich verstehe. Also:
>
> [mm]\bruch{m!}{m^k(m-k)!} < \bruch{n!}{n^k(n-k)!}[/mm]
>
Genau so würde ich es machen. Und bei [mm]\frac{m!}{(m-k)!}[/mm] bleiben genau $k$ Faktoren stehen (ebenso bei [mm]\frac{n!}{(n-k)!}[/mm]), die man einzeln vergleichen kann.
Gruß
pits
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:23 So 21.10.2012 | | Autor: | reverend |
Hallo pits, hallo Apfelchips,
> > Also:
> >
> > [mm]\bruch{m!}{m^k(m-k)!} < \bruch{n!}{n^k(n-k)!}[/mm]
> >
>
> Genau so würde ich es machen. Und bei [mm]\frac{m!}{(m-k)!}[/mm]
> bleiben genau [mm]k[/mm] Faktoren stehen (ebenso bei
> [mm]\frac{n!}{(n-k)!}[/mm]), die man einzeln vergleichen kann.
Ja, das wäre noch kein Problem. Aber da steht ja noch mehr - nämlich [mm] m^k [/mm] bzw. [mm] n^k [/mm] im Nenner. Da muss man doch noch etwas mehr argumentieren.
Dabei wird die Ungleichung [mm] \left(1-\bruch{i}{m}\right)<\left(1-\bruch{i}{n}\right) [/mm] eine Rolle spielen. 
Übrigens ist nach wie vor der Fall [mm] m
Grüße
reverend
|
|
|
| |
|
Hallo Apfelchips,
damit ist diese Aufgabe noch nicht erledigt.
> > Das k kann verschiedene Werte annehmen und deshalb sollte
> > man das nicht festlegen. Wichtig ist hier nur, dass [mm]k\leq n[/mm].
>
> Ich dachte mir schon fast, dass das, was ich versucht habe
> zu zeigen, nicht allgemein genug ist.
>
> > Also "einfach" mit der Ungleichung losrechnen (z.B. erst
> > mal auf beiden Seiten mit [mm]k![/mm] multiplizieren. Ich würde
> > dann die Terme mit k auf eine Seite bringen und die anderen
> > auf die andere, aber da muss man dann selbst mal schauen.
>
> Ich hab's mal gewagt und die Ungleichung (genau so)
> umgeformt. Die Zwischenschritte poste ich jetzt nicht (es
> sei denn, das Ergebnis meiner Umformungsarbeiten ist
> falsch):
>
> [mm]\bruch{(n-k)!}{(m-k)!} < \bruch{n!}{m!}[/mm]
>
> k als Subtrahend im Zähler und Nenner des linken Bruchs
> sorgt dafür, dass der linke Ausdruck stets kleiner ist als
> der rechte (da [mm]k \geq 1[/mm]).
Da ist die Argumentation von pits (die hier folgt) deutlich klarer: Es sind jeweils (n-m) Faktoren, und die linken sind kleiner als die rechten.
Allerdings ist mit dieser Rechnung und Argumentation nur der Fall [mm] $k\le [/mm] m<n$ erledigt, denn Du hast hier die Standarddefinition der Binomialkoeffizienten verwendet. Da muss in [mm] \vektor{m\\k} [/mm] gelten: [mm] k\le{m}.
[/mm]
Offen bleibt nun aber noch der Fall [mm] m
Schau Dir dazu mal die ![[]](/images/popup.gif) verallgemeinerte Definition an.
Du wirst für den noch offenen Fall mit k>m nun leicht zeigen können, dass [mm] \vektor{m\\k}=0 [/mm] ist.
> War das alles?
Nein, eben nicht.
Grüße
reverend
|
|
|
| |
|
Hätte da mal eine dumme Frage: Wenn ich die von reverend angesprochene allgemeine Definition des Binomialkoeffizienten für die erste Ungleichung benutze erhalte ich doch theoretisch:
[mm] \bruch{m*...*(m-(k-1))}{k!} [/mm] < [mm] \bruch{n*...*(n-(k-1))}{k!}
[/mm]
Sehe ich das richtig?
Und wenn man daruas jetzt durch beidseitige Multiplikation von k!
[mm] m\cdot{}...\cdot{}(m-(k-1)) [/mm] < [mm] n\cdot{}...\cdot{}(n-(k-1))
[/mm]
macht, heißt das doch unter der Vorraussetzung m<n, die in der Aufgabenstellung gegeben ist, dass der linke Teil kleiner als der rechte sein muss, oder mache ich mir das da zu einfach?
|
|
|
| |
|
Hallo HuntingShadow, ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
> Hätte da mal eine dumme Frage:
Antworten können dumm sein (s.u.), Fragen doch aber nicht.
> Wenn ich die von reverend
> angesprochene allgemeine Definition des
> Binomialkoeffizienten für die erste Ungleichung benutze
> erhalte ich doch theoretisch:
>
> [mm]\bruch{m*...*(m-(k-1))}{k!}[/mm] < [mm]\bruch{n*...*(n-(k-1))}{k!}[/mm]
>
> Sehe ich das richtig?
> Und wenn man daruas jetzt durch beidseitige Multiplikation
> von k!
>
> [mm]m\cdot{}...\cdot{}(m-(k-1))[/mm] < [mm]n\cdot{}...\cdot{}(n-(k-1))[/mm]
>
> macht, heißt das doch unter der Vorraussetzung m<n, die="" in="" <br="">> der Aufgabenstellung gegeben ist, dass der linke Teil
> kleiner als der rechte sein muss, oder mache ich mir das da
> zu einfach?
Wie mans nimmt. In der Tat sieht es sogar so aus, als könnte die linke Seite sogar größer werden als die rechte, je nachdem wie groß die Beträge der negativen Faktoren werden. Allerdings können die n nicht übersteigen und bei genauerer Betrachtung droht tatsächlich keine Gefahr.
Viel einfacher aber ist die Überlegung, dass für den jetzt betrachteten Fall [mm] m
Grüße
reverend
</n,>
|
|
|
|
