Binomialkoeffizient/Teilmengenanzahl/Fakt/Beweis/Aufgabe/Lösung

Wir beweisen die Aussage durch Induktion nach $n$. Die Aussage ist für $n=0$ klar, sei also angenommen, die Aussage sei für ein beliebiges $n$ (für alle $k$) schon bewiesen, und betrachten wir eine $(n+1)$-elementige Menge $M$. Diese Menge ist wegen $n\ge 0$ nicht leer. Wir fixieren ein Element $a\in M$ und betrachten die $n$-elementige Teilmenge $M\setminus \{a\}\subset M$. Jede Teilmenge von $M$ enthält entweder $a$ oder nicht. Daher lassen sich die $k$-elementigen Teilmengen von $M$ aufteilen in $k$-elementige Teilmengen von $M\setminus \{a\}$ (das sind diejenigen Teilmengen, die nicht $a$ enthalten), und die $(k-1)$-elementigen Teilmengen von $M\setminus \{a\}$ (eine solche $(k-1)$-elementige Teilmenge $T$ definiert die $k$-elementige Teilmenge $T\cup \{a\}$ in $M$). Daher ist die Gesamtzahl der $k$-elementigen Teilmengen von $M$ nach Fakt gleich

$(\genfrac{}{}{0ex}{}{n}{k})+(\genfrac{}{}{0ex}{}{n}{k-1})=(\genfrac{}{}{0ex}{}{n+1}{k}).$

Zur gelösten Aufgabe