Direkt zum Inhalt
  1. Startseite
  2. Quests
  3. #371

Aufgabe mit Lösung 2 Beziehungen für Binomialkoeffizienten beweisen

Zeige folgende Beziehungen für Binomialkoeffizienten:

  1. \[ \text{C}(N+M-1; M) ~=~ \text{C}(N+M-1; N-1) \]
  2. \[ \sum_{k=0}^M \text{C}(N+k; N) ~=~ \text{C}(N+1+k; N+1) \]
Lösungstipps

Benutze sowohl bei Aufgabenteil (a) als auch bei (b) die Definition des Binomialkoeffizienten aus der Kombinatorik und beweise (b) mithilfe der vollständigen Induktion.

Lösung

Lösung zu (a) anzeigen

Hier benutzt Du einfach die Definition des Binomialkoeffizienten:\[ \text{C}(N+M-1; M) ~=~ \frac{(N ~+~ M ~-~ 1)!}{M! ~(N ~+~ M ~-~ 1 ~-~ M)!} ~=~ \frac{(N ~+~ M ~-~ 1)!}{M! ~(N ~-~ 1)!} ~=~ \frac{(N ~+~ M ~-~ 1)!}{(N ~-~ 1)! ~ (N ~+~ M ~-~ 1 ~-~(N~-~1))!} ~=~ \text{C}(N+M-1; N-1) \]

Hierbei wurde nach dem dritten Gleichheitszeichen \( M ~=~ N ~+~ M ~-~ 1 ~-~(N~-~1) \) umgeschrieben, damit man die Definition des Binomialkoeffizienten benutzen kann.

Lösung zu (b) anzeigen

Induktionsanfang: Sei \( M ~=~ 0 \), dann:\[ \sum_{k=0}^0 \text{C}(N+k; N) ~=~ \text{C}(N+0; N) ~=~ \text{C}(N; N) ~=~ \frac{N!}{N! (N-N)!} ~=~ \frac{N!}{N!} ~=~ 1 \]

Weiter lässt sich schreiben:\[ 1 ~=~ \frac{(N+1)!}{(N+1)!} ~=~ \frac{(N+1)!}{(N+1)! ~ (N+1 ~-~ N+1)!} ~=~ \text{C}(N+1; N+1) \]

Es funktioniert! Denn das Ergebnis entspricht genau der rechten Seite der zu beweisenden Gleichung, wenn man in sie \( M ~=~ 0 \) einsetzt.

Induktionvoraussetzung: Wir nehmen an, dass die zu beweisende Gleichung gilt:\[ \sum_{k=0}^M \text{C}(N+k,N) ~=~ \text{C}(N+1+k; N+1) \]

Induktionsschritt: Betrachte den Fall \( M ~+~ 1 \):\[ \sum_{k=0}^{M+1} \text{C}(N+k; N) \]

Diese Summe kannst Du aufspalten, sodass Du die Induktionvoraussetzung benutzen kannst:\[ \sum_{k=0}^{M} \text{C}(N+k; N) ~+~ \text{C}(N+M+1; N) \]

Nun kannst Du die Induktionvoraussetzung einsetzen:\[ \text{C}(N+1+M; N+1) ~+~ \text{C}(N+M+1; N) \]

Benutze die Definition des Binomialkoeffizienten:\[ \frac{(N+1+M)!}{(N+1)! ~ M!} ~+~ \frac{(N+1+M)!}{N! ~ (M+1)!} \]

Klammere erstmal \( (N+1+M)! \) aus und bringe alles auf den gleichen Nenner:\[ (N+1+M)! ~ \left( \frac{N!~(M+1)! ~+~ (N+1)!M!}{(N+1)! ~ M! ~ N! ~ (M+1)!} \right) \]

Benutze die Definition der Fakultät, indem Du \( M+1 \)-Faktor und \( N+1 \)-Faktor herausziehst:\[ (N+1+M)! ~ \left( \frac{N! ~ M!~(M+1) ~+~ (N+1) ~ N!~M!}{(N+1)! ~ M! ~ N! ~ (M+1)!} \right) \]

Kürze \( N! ~ M! \) und fasse zusammen:\[ (N+1+M)! ~ \left( \frac{M+2~+~ N}{(N+1)! ~ (M+1)!} \right) \]

Nach der Definition der Fakultät kannst Du \( M+2+N \) in die ausgeklammerte Fakultät reinziehen:\[ \frac{(N+2+M)!}{(N+1)! ~ (M+1)!} \]

Um die Definition des Binomialkoeffizienten anwenden zu können schreibst Du \( (M+1)! \) um:\[ \frac{(N+2+M)!}{(N+1)! ~ (N+2+M - (N+1))!} \]

Das entspricht nach der Definition genau folgendem Binomialkoeffizienten:\[ \text{C}(N+2+M; N+1) ~=~ \text{C}(N+1+(M+1); N+1) \]

Der Induktionsschritt ist erfüllt:\[ \sum_{k=0}^{M+1} \text{C}(N+k; N) ~=~ \text{C}(N+1+(M+1); N+1) \]

Damit gilt auch die zu zeigende Gleichung.

Details zum Inhalt
  • Die Quest wurde hinzugefügt von FufaeV am .
  • Die Quest wurde aktualisiert von FufaeV am .

Feedback geben

Hey! Ich bin Alexander FufaeV, der Physiker und Autor hier. Es ist mir wichtig, dass du stets sehr zufrieden bist, wenn du hierher kommst, um deine Fragen und Probleme zu klären. Da ich aber keine Glaskugel besitze, bin ich auf dein Feedback angewiesen. So kann ich Fehler beseitigen und diesen Inhalt verbessern, damit auch andere Besucher von deinem Feedback profitieren können.

Wie zufrieden bist Du?