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


Es sei fixiert. Bei gibt es nur die leere Menge, was mit dem Binomialkoeffizienten

übereinstimmt. Es sei die Aussage also für ein zwischen und schon bewiesen. Jeder -elementigen Teilmenge von und jedem der Elemente aus kann man die -elementige Menge

zuordnen. Dabei wird jede -elementige Menge erreicht, und zwar -fach, da man ja aus jedes der Elemente herausnehmen kann. Zwischen der Anzahl der -elementigen Teilmengen von und der Anzahl der -elementigen Teilmengen von besteht also der Zusammenhang

Unter Verwendung der Induktionsvoraussetzung ist daher