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

Es sei ${}n$ fixiert. Bei ${}k=0$ gibt es nur die leere Menge, was mit dem Binomialkoeffizienten

${}{\binom {n}{0}}=1\,$

übereinstimmt. Es sei die Aussage also für ein ${}k$ zwischen ${}0$ und ${}n-1$ schon bewiesen. Jeder ${}k$-elementigen Teilmenge ${}S$ von ${}M$ und jedem der ${}n-k$ Elemente ${}x$ aus ${}M\setminus S$ kann man die ${}k+1$-elementige Menge

${}T=S\cup \{x\}\,$

zuordnen. Dabei wird jede ${}k+1$-elementige Menge ${}T$ erreicht, und zwar ${}k+1$-fach, da man ja aus ${}T$ jedes der ${}k+1$ Elemente herausnehmen kann. Zwischen der Anzahl ${}A_{k}$ der ${}k$-elementigen Teilmengen von ${}M$ und der Anzahl ${}A_{k+1}$ der ${}k+1$-elementigen Teilmengen von ${}M$ besteht also der Zusammenhang

${}A_{k+1}\cdot (k+1)=A_{k}\cdot (n-k)\,.$

Unter Verwendung der Induktionsvoraussetzung ist daher

${}{\begin{aligned}A_{k+1}&={\frac {n-k}{k+1}}A_{k}\\&={\frac {n-k}{k+1}}{\binom {n}{k}}\\&={\frac {n-k}{k+1}}\cdot {\frac {n(n-1)\cdots (n-k+1)}{k!}}\\&={\frac {n(n-1)\cdots (n-k+1)(n-k)}{(k+1)!}}\\&={\binom {n}{k+1}}\end{aligned}}$

Zur gelösten Aufgabe