Wenn Sie das Buch noch nicht kennen, dann können Sie hier weitere Informationen finden.

Lösung für Aufgabe 2.5.17

In manchen Büchern wird der Binomialkoeffizient durch seine geschlossene Formel definiert, also durch \begin{equation} \binom nk := \begin{cases} 0 & \text{falls $n<0$ oder $k>n$}\\ \displaystyle\frac{n!}{k!(n-k)!} & \text{sonst.} \end{cases} \end{equation} In diesem Fall muss die rekursive Darstellung (unsere Definition) bewiesen werden. Um dies nachzuvollziehen, nehmen Sie an, dass (2.5.17) gilt und beweisen Sie, dass dann auch $$ \binom{0}{0}=1\quad \text{und}\quad \binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k} $$ gelten.


Zunächst zeigen wir, dass $\binom00 = 1$ gilt: $$\binom{0}{0}=\frac{0!}{0!\cdot(0-0)!}=\frac1{1\cdot1}=1.$$

Nun bleibt noch, die Rekursion zu zeigen.

Es gilt \begin{eqnarray*} \binom{n-1}{k-1}+\binom{n-1}{k} &=&\frac{(n-1)!}{(k-1)!(n-1-k+1)!}+\frac{(n-1)!}{k!(n-1-k)!}\\ &=&\frac{(n-1)!}{(k-1)!(n-k)(n-k-1)!}+\frac{(n-1)!}{k(k-1)!(n-k-1)!}\\ &=&\frac{k(n-1)!+(n-k)(n-1)!}{k(k-1)!(n-k)(n-k-1)!}=\frac{n\cdot(n-1)!}{k!(n-k)!}=\frac{n!}{k!(n-k)!}=\binom{n}{k} \end{eqnarray*} $\Box$