1. Welt
  2. Aufgaben
  3. #613

Aufgaben: 2 Beziehungen für Binomialkoeffizienten beweisen

Vorkenntnisse anzeigen

Aufgabenstellung

Zeige folgende Beziehungen für Binomialkoeffizienten:

  1. \[ \left(\begin{array}{c} N+M-1\\ M \end{array}\right) ~=~ \left(\begin{array}{c} N+M-1\\ N-1 \end{array}\right) \]
  2. \[ \sum_{k=0}^M \left(\begin{array}{c} N+k \\ N \end{array}\right) ~=~ \left(\begin{array}{c} N+1+k \\ N+1 \end{array}\right) \]
Allgemeine 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ösungen zur Aufgabe

Lösung zu (a) anzeigen

Hier benutzt Du einfach die Definition des Binomialkoeffizienten: \[ \left(\begin{array}{c} N+M-1\\ M \end{array}\right) ~=~ \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))!} ~=~ \left(\begin{array}{c} N+M-1\\ N-1 \end{array}\right) \]

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 \left(\begin{array}{c} N+k \\ N \end{array}\right) ~=~ \left(\begin{array}{c} N+0 \\ N \end{array}\right) ~=~ \left(\begin{array}{c} N \\ N \end{array}\right) ~=~ \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)!} ~=~ \left(\begin{array}{c} N+1 \\ N+1 \end{array}\right) \]

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 \left(\begin{array}{c} N+k \\ N \end{array}\right) ~=~ \left(\begin{array}{c} N+1+k \\ N+1 \end{array}\right) \]

Induktionsschritt: Betrachte den Fall \( M ~+~ 1 \): \[ \sum_{k=0}^{M+1} \left(\begin{array}{c} N+k \\ N \end{array}\right) \]

Diese Summe kannst Du aufspalten, sodass Du die Induktionvoraussetzung benutzen kannst: \[ \sum_{k=0}^{M} \left(\begin{array}{c} N+k \\ N \end{array}\right) ~+~ \left(\begin{array}{c} N+M+1 \\ N \end{array}\right) \]

Nun kannst Du die Induktionvoraussetzung einsetzen: \[ \left(\begin{array}{c} N+1+M \\ N+1 \end{array}\right) ~+~ \left(\begin{array}{c} N+M+1 \\ N \end{array}\right) \]

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: \[ \left(\begin{array}{c} N+2+M \\ N+1 \end{array}\right) ~=~ \left(\begin{array}{c} N+1+(M+1) \\ N+1 \end{array}\right) \]

Der Induktionsschritt ist erfüllt: \[ \sum_{k=0}^{M+1} \left(\begin{array}{c} N+k \\ N \end{array}\right) ~=~ \left(\begin{array}{c} N+1+(M+1) \\ N+1 \end{array}\right) \]

Damit gilt auch die zu zeigende Gleichung.

Weltkarte
Community
ONLINE 1
Gäste online: 1
Denker online: 0
Wenn Du auch etwas reinschreiben möchtest, musst Du Dich einloggen!
Verwalten

Inhalt hinzufügen

Profil

Einloggen

Mitmachen?

  • Deine hinzugefügten Inhalte nachträglich bearbeiten
  • Deine noch nicht freigeschaltete Inhalte ansehen
  • Alle Bilder-Download-Optionen benutzen
  • Im Mini-Chat schreiben
  • Anderen Benutzern PM verschicken (Benutzer-Bereich noch nicht so gut ausgebaut)
Mitmachen