1. Welt
  2. Quests
  3. #613
Alexander Fufaev

2 Beziehungen für Binomialkoeffizienten beweisen

aus dem Bereich: Quests
Optionen

Deine Aufgabe ist...

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) \]
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ö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.

Weltkarte
Verwalten
Profil
Die Stimme fragt...
Wie erlange ich den Zugang?

Um das Portal von Ak'tazun betreten zu können, musst Du die rote Pille schlucken. Nachdem Du durch das Portal gegangen bist, gelangst Du in die Matrix, wo Du beispielsweise folgendes tun kannst:

  • Inhalte hinzufügen & verwalten
  • Einige Inhalte kommentieren
  • Mittels Kommunikator RT2000 chatten
  • WhatsApp-Gruppe beitreten
Bist Du dabei?
Ja, bin dabei!
Portale in die anderen Welten

Reise zu den sicheren anderen Welten des Internets, um nach dem Wissen zu suchen. Findest Du eine Welt ("Internetseite" :D) besonders interessant, dann kannst Du in der Universaldenkerwelt ein Portal zu dieser Welt erbauen, um den anderen Besuchern den schnellen Zugang dazu zu gewährleisten.

Portalraum betreten
Kommunikator
ONLINE 7
Gäste online: 7
Denker online: 0
Der Kommunikator RT2000 funktioniert nur innerhalb der Matrix!
Ich will in die Matrix!Mayday! Kontakt aufnehmen.