Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Beweis (n über k) < (n über l) mit l<=n/2

Beweis (n über k) < (n über l) mit l<=n/2

Universität / Fachhochschule

Binomialkoeffizienten

Tags: Beweis, Binomialkoeffizient, Induktion

Steffi021 aktiv_icon

19:01 Uhr, 17.10.2009

Hallo!
Ich wollte mich an einem Übungsbeweis versuchen, der mir nicht so recht gelingen will

: (

Die Aufgabe:

n, l

ℕ

mit

l \leq \frac{n}{2}

Beweisen für

0 \leq k < l

gilt:

(\begin{matrix} n \\ k \end{matrix}) < (\begin{matrix} n \\ l \end{matrix})

Mein Ansatz:
Ich hatte mir überlegt die Aufgabe per Induktion zu lösen.
Im Induktionsschritt

k = 0

klappt das ja noch super.

1 < (\begin{matrix} n \\ l \end{matrix})

kann man gut begründen, da

(\begin{matrix} n \\ l \end{matrix})

nicht kleiner gleich 1 werden kann lt. Vor.

Aber dann beim Schritt

k = k + 1

hörts auf. Wie beweise ich die allgemeine Gültigkeit der Formel? Gibt es da Tricks oder Hintergrundwissen, auf das ich zurückgreifen müsste?

Bin über jede Hilfe sehr dankbar!!

Viele Grüße,
Steffi

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Kombinatorik: Ziehen ohne Reihenfolge und ohne Zurücklegen

Zu diesem Thema passende Musteraufgaben einblenden

michaL aktiv_icon

19:45 Uhr, 17.10.2009

Hallo Steffi,

eine vollständige Induktion scheint mir in diesem Fall ganz unnötig und auch sehr schwierig. Zunächst mal eine Analyse, warum es dir mit Induktion nicht gelungen ist:
Du hattest keinen Zusammenhang (Formel) zwischen

(\binom{n}{k}) = \frac{n!}{k! \cdot (n - k)!}

und

(\binom{n}{k + 1}) = \frac{n!}{(k + 1)! \cdot (n - (k + 1))!}

. Normalerweise führt man beim Induktionsschritt auf einen Vorgänger zurück, dafür braucht man aber so eine Formel:

(\binom{n}{k + 1}) = (\binom{n}{k}) \cdot \frac{n - k}{k + 1}

.
Aber selbst damit scheint mir die Induktion schwierig. Warum? Nun, das einzige, was sich ändert im Vergleich ist die kleinere Seite (also links vom Kleinerzeichen). Nur das Wissen, dass der Koeffizient weiter weg von der Mitte kleiner ist, hilft mir nicht viel. Wenn ich wüsste, um welchen Teil er kleiner ist, dann könnte ich den Wert mit

\frac{n - k}{k + 1}

multiplizieren und schauen, ob ich unterhalb von 1 bleibe (Beispiel:

(\binom{n}{k})

ist 35% von

(\binom{n}{l})

, dann ist

(\binom{n}{k + 1})

35%

\cdot \frac{n - k}{k + 1}

von

(\binom{n}{l})

.)
Um so an die Sache rangehen zu können, müsstest du für jedes

n

und jedes

l

und für alle

k < l

eine einigermaßen genaue Abstandsformel haben. Scheint ein mühseliges Unterfangen zu sein.

Alternative: Eigentlich muss man ja nur zeigen, dass die Binomialkoeffizienten zur Mitte hin immer größer werden, d.h. man zeigt (von mir aus auch induktiv), dass für bel.

n

und

k

so, dass

k + 1 \leq \frac{n}{2}

(\binom{n}{k}) < (\binom{n}{k + 1})

gilt.

So, das kannst du ja mal versuchen zu formalisieren. Dazu kannst du die Rekursionsformel verwenden.

Mfg Michael

Steffi021 aktiv_icon

09:09 Uhr, 19.10.2009

Hallo und danke für deine schnelle Antwort!
Okay, Induktion scheint mir nun auch nicht mehr so angebracht :-)

Ich komme nur mit einer Sache nicht so ganz zurecht:
Wenn ich beweise, dass

(\begin{matrix} n \\ k \end{matrix}) < (\begin{matrix} n \\ k + 1 \end{matrix}),

dann bedeutet das doch, dass

l = k + 1,

was aber laut Voraussetzung nicht gegeben ist.
Oder habe ich gerade einen Denkfehler?

Edddi aktiv_icon

10:34 Uhr, 19.10.2009

...wenn

(\begin{matrix} n \\ k \end{matrix}) < (\begin{matrix} n \\ k + 1 \end{matrix})

dann gilt nach Induktion

k \to (k + 1) :

(\begin{matrix} n \\ k + 1 \end{matrix}) < (\begin{matrix} n \\ k + 2 \end{matrix})

und somit:

(\begin{matrix} n \\ k \end{matrix}) < (\begin{matrix} n \\ k + 1 \end{matrix}) < (\begin{matrix} n \\ k + 2 \end{matrix})

und somit:

(\begin{matrix} n \\ k \end{matrix}) < (\begin{matrix} n \\ k + 1 \end{matrix}) < (\begin{matrix} n \\ k + 2 \end{matrix}) < (\begin{matrix} n \\ k + 3 \end{matrix}) < ...

usw.

;-)

Steffi021 aktiv_icon

10:48 Uhr, 19.10.2009

ACHSO!!

Super, danke!

Aber reicht das als Beweis? Man muss also bei so einer Aufgabe nicht noch zeigen, dass das Ergebnis(!) einer

(\begin{matrix} n \\ k \end{matrix}) -

Formel größer wird wenn

k

größer wird?

Edddi aktiv_icon

11:04 Uhr, 19.10.2009

du wolltest zeigen das gilt:

(\begin{matrix} n \\ k \end{matrix}) < (\begin{matrix} n \\ l \end{matrix})

wenn du definierst, das

k < l < \frac{n}{2},

dann reicht es zu zeigen, das:

(\begin{matrix} n \\ k \end{matrix}) < (\begin{matrix} n \\ k + 1 \end{matrix})

da dann auch

(\begin{matrix} n \\ k \end{matrix}) < (\begin{matrix} n \\ k + 1 \end{matrix}) < (\begin{matrix} n \\ k + 1 \end{matrix}) < ... < (\begin{matrix} n \\ l \end{matrix})

ist.

Dies musst du allerding beweisen!

(\begin{matrix} n \\ k \end{matrix}) < (\begin{matrix} n \\ k + 1 \end{matrix})

\frac{n!}{(k!) \cdot (n - k)!} < \frac{n!}{(k + 1)! \cdot (n - k - 1)!}

(k!) \cdot (n - k)! > (k + 1)! \cdot (n - k - 1)!

..jetzt die Fakultätengesetze anwenden:

(k!) \cdot (n - k)! > k! \cdot (k + 1) \cdot \frac{(n - k)!}{n - k}

...und den Rest allein...

;-)

michaL aktiv_icon

16:18 Uhr, 19.10.2009

Hi zusammen,

ich könnte mir vorstellen, dass du folgendes denkst: Warum soll ich bei dem speziellen

l

aufhören mit dem schicken Beweis, wenn es doch offenbar noch weiter geht.
Dazu kann ich dir nur sagen, dass der Faktor

\frac{(\binom{n}{k + 1})}{(\binom{n}{k})}

nicht immer größer als 1. Und jetzt kannst du dir überlegen, wann diese Serie endet.

Mfg MIchael

Steffi021 aktiv_icon

22:57 Uhr, 20.10.2009

Vielen Dank an euch!
Ich glaube, dass ich es soweit gelöst habe. Morgen haben wir Übungsgruppe, da werd ich mal schauen, obs gestimmt hat und hier dann der Vollständigkeithalber noch die Endlösung posten :-)

ArnoNuem aktiv_icon

15:17 Uhr, 14.11.2009

Hab mal ne Frage zu der Aufgabe:

Es wird folgendes geschrieben:

"du wolltest zeigen das gilt:

(n

über

k) < (n

über

l)

wenn du definierst, das

k < l < \frac{n}{2},

dann reicht es zu zeigen, das:

(n

über

k) < (n

über k+1)"

Hier versteh ich nicht ganz, warum

k + 1

ebenfalls kleiner als

l

sein soll. Man hat doch nur definiert, dass

k < l

sein soll. Ich glaub ich überseh iwas, oder komm einfach nicht drauf. Helft mir bitte.

Steffi021 aktiv_icon

17:15 Uhr, 15.11.2009

Leider war mein (und somit auch teils eurer) Lösungsweg komplett falsch.
Ich habe Null Punkter auf die Aufgabe bekommen und ausgewertet haben wir sie auch noch nicht.
Ich hoffe sehr, dass wir das noch tun werden und dann kann ich hier auch noch die korrekte Lösung posten.

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

678277

660943

	Status: nicht eingeloggt	Noch nicht registriert?