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

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.

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.