Aloha :)
Zu zeigen: Es gibt genau \(\binom{n}{k}\) Möglichkeiten, um aus einer n-elementigen Menge k Elemente auszuwählen.
Induktions-Verankerung bei \(n=0\):
Eine Menge \(M_0\) mit \(n=0\) Elementen ist die leere Menge. Aus dieser Menge kann man genau eine Menge, nämlich die leere Menge an sich, auswählen. Diese hat \(k=0\) Elemente. Tatsächlich ist \(\binom{0}{0}=1\).
Induktions-Verankerung bei \(n=1\):
Aus einer Menge \(M_1\) mit \(n=1\) Element kann man genau eine 0-elementige Menge auswählen, nämlich die leere Menge, und genau eine 1-elementige Menge auswählen, nämlich die Menge \(M_1\) selbst. Tatsächlich gilt: \(\binom{1}{0}=\binom{1}{1}=1\).
Induktionsschritt \(n\to n+1\):
Wir gehen von einer \(n\)-elementigen Menge \(M_n\) aus und fügen ein neues Element hinzu, um eine \((n+1)\)-elementige Menge \(M_{n+1}\) zu erhalten. Wenn wir aus \(M_{n+1}\) nun \(k\) Elemente auswählen wollen, können 2 Fälle unterschieden werden:
1. Fall: Das neue Element wird nicht ausgewählt...
dann müssen \(k\) Elemente aus der Menge \(M_n\) stammen. Dafür gibt es nach Induktionsvoraussetzung \(\binom{n}{k}\) Möglichkeiten.
2. Fall: Das neue Element wird ausgewählt...
dann müssen \((k-1)\) Elemente aus der Menge \(M_n\) stammen. Dafür gibt es nach Induktionsvoraussetzung \(\binom{n}{k-1}\) Möglichkeiten.
Beide Fälle zusammengezählt ergeben:$$\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}$$Das ist eine mögiche (rekursive) Definitionsgleichung für den Binomialkoeffizienten. Wenn ihr die in der Vorlesung hattet, bist du jetzt fertig. Falls nicht, musst du ihre Gültigkeit noch zeigen.
