Direkt zum Inhalt
  1. Startort
  2. Quests
  3. 📖
Level 4
Level 4 setzt das Wissen über die Vektorrechnung, (mehrdimensionale) Differential- und Integralrechnung voraus. Geeignet für fortgeschrittene Studenten.

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

Zeige folgende Beziehungen für Binomialkoeffizienten:

  1. 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. 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.

Details zum Inhalt
  • Die Quest wurde hinzugefügt von FufaeV am .
  • Die Quest wurde aktualisiert von FufaeV am .