Beweis von Beziehung zwischen < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
|
Hi, wie kann ich folgende Beziehung zwischen Binomialkoeffizienten beweisen:
[mm] \vektor{n \\ k-1} [/mm] + [mm] \vektor{n \\ k} [/mm] = [mm] \vektor{n+1 \\ k}
[/mm]
Ich hoffe die Schreibweise ist richtig, soll "n über k" und so sein...
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:14 Sa 16.04.2005 | | Autor: | Hanno |
Hallo Codemaster!
Bekanntlich gibt der Binomialkoeffizient [mm] $\vektor{n+1\\ k}$ [/mm] an, wie viele Möglichkeiten es dafür gibt, $k$ Elemente aus einer $(n+1)$-elementigen Menge auszuwählen. Wir unterscheiden die Auswahlen nun hinsichtlich der Frage, ob das $n+1$-te Element in der Auswahl der $k$ Elemente enthalten ist oder nicht. Ist das $n+1$-te Element nicht enthalten, so müssen wir aus den verbleibenden $n$ Elementen noch alle $k$ auswählen, wofür es [mm] $\vektor{n\\ k}$ [/mm] Möglichkeiten gibt. Ist in unserer Auswahl das $n+1$-te Element enthalten, so bleiben noch $k-1$ Elemente aus den übrigen $n$ auszuwählen, wofür es [mm] $\vektor{n\\ k-1}$ [/mm] Möglichkeiten gibt. Damit ergibt sich [mm] $\vektor{n+1\\ k}=\vektor{n\\ k}+\vektor{n\\ k-1}$, [/mm] was zu zeigen war.
So, das war (hoffentlich) schön anschaulich; man kann das Ganze natürlich aber auch rein formell begründen, indem man die Binomialkoeffizienten ausschreibt:
[mm] $\vektor{n+1\\k}=\vektor{n\\ k}+\vektor{n\\ k-1}$
[/mm]
[mm] $\gdw\frac{(n+1)!}{(n+1-k)!k!}=\frac{n!}{k!(n-k)!}+\frac{n!}{(k-1)!(n-(k-1))!}$
[/mm]
Wir multiplizieren mit $k!$, $(n+1-k)!$ und teilen durch $n!$:
[mm] $\gdw [/mm] n+1=n+1-k+k$,
was offensichtlich richtig ist [Wenn du magst, kannst du diese drei Schritte auch ausführlicher aufschreiben, ich habe aber wirklich nur die genannten Schritte vorgenommen].
Ich hoffe, dass ich dir helfen konnte.
Liebe Grüße,
Hanno
|
|
|
|
