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$