Binomialkoeffizient/Teilmengenanzahl/Fakt/Beweis

Beweis

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\geq 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

${}{\binom {n}{k}}+{\binom {n}{k-1}}={\binom {n+1}{k}}\,.$

Zur bewiesenen Aussage