Level 4
Aufgabe mit Lösung 2 Beziehungen für Binomialkoeffizienten beweisen
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\[ \underset{k~=~0}{\overset{M}{\boxed{+}}} ~ \left(\begin{array}{c} N+k \\ N \end{array}\right) ~=~ \left(\begin{array}{c} N+1+M \\ N+1 \end{array}\right) \]
Lösungstipps
Benutze sowohl bei Aufgabenteil (a) als auch bei (b) die Definition des Binomialkoeffizienten aus der Kombinatorik \[ \left(\begin{array}{c} A \\ B \end{array}\right) ~=~ \frac{A!}{B! ~(A ~-~ B)!} \]und beweise (b) mithilfe der vollständigen Induktion.
Lösungen
Lösung für (a)
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}
Lösung für (b)
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.