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

Benutze die Definition des Binomialkoeffizienten aus dem Lösungshinweis:3\begin{align} \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)!} \end{align}

Erweitere \(M!\) mit einer Null, indem du \(N-1\) draufaddierst und wieder abziehst: \( M ~=~ N ~+~ M ~-~ 1 ~-~(N~-~1) \). Benutze anschließend die Definition des Binomialkoeffizienten rückwärts:3.1\begin{align} \left(\begin{array}{c} N+M-1 \\ M \end{array}\right) ~&=~ \frac{(N ~+~ M ~-~ 1)!}{(N ~-~ 1)! ~ (N ~+~ M ~-~ 1 ~-~(N~-~1))!} \\\\ ~&=~ \left(\begin{array}{c} N+M-1 \\ N-1 \end{array}\right) \end{align}

Für diesen Aufgabenteil benutzen wir den Induktionsbeweis.

Induktionsanfang
Sei \( M ~=~ 0 \), dann:4\begin{align} \underset{k~=~0}{\overset{0}{\boxed{+}}} ~ \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 \end{align}

Die in 4 herausgekommene 1 können wir auch folgendermaßen schreiben:5\begin{align} 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) \end{align}

Der Indunktionsanfang mit \( M = 0 \) ist erfüllt.

Induktionvoraussetzung
Wir nehmen an, dass die zu beweisende Gleichung für beliebiges \(M\) gilt:6\[ \underset{k~=~0}{\overset{M}{\boxed{+}}} ~ \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 \):7\[ \underset{k~=~0}{\overset{M+1}{\boxed{+}}} ~ \left(\begin{array}{c} N+k \\ N \end{array}\right) \]

Als nächstes spalten wir 7 in zwei Anteile auf, sodass wir die Induktionsvoraussetzung 6 benutzen können:8\[ \underset{k~=~0}{\overset{M}{\boxed{+}}} ~ \left(\begin{array}{c} N+k \\ N \end{array}\right) ~+~ \left(\begin{array}{c} N+M+1 \\ N \end{array}\right) \]

Nun kannst du den linken Summanden in 8 mit der Induktionvoraussetzung 6 ersetzen:9\[ \left(\begin{array}{c} N+1+M \\ N+1 \end{array}\right) ~+~ \left(\begin{array}{c} N+M+1 \\ N \end{array}\right) \]

Ersetze die beiden Summanden mit der Definition des Binomialkoeffizienten:10\[ \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:11\[ (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:12\[ (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:13\[ (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:14\[ \frac{(N+2+M)!}{(N+1)! ~ (M+1)!} \]

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

Das entspricht nach der Definition genau folgendem Binomialkoeffizienten:16\[ \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:17\[ \underset{k~=~0}{\overset{M+1}{\boxed{+}}} ~ \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.