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

Aus Wikiversity


Wir beweisen die Aussage durch Induktion nach . Die Aussage ist für klar, sei also angenommen, die Aussage sei für ein beliebiges (für alle ) schon bewiesen, und betrachten wir eine -elementige Menge . Diese Menge ist wegen nicht leer. Wir fixieren ein Element und betrachten die -elementige Teilmenge . Jede Teilmenge von enthält entweder oder nicht. Daher lassen sich die -elementigen Teilmengen von aufteilen in -elementige Teilmengen von (das sind diejenigen Teilmengen, die nicht enthalten), und die -elementigen Teilmengen von (eine solche -elementige Teilmenge definiert die -elementige Teilmenge in ). Daher ist die Gesamtzahl der -elementigen Teilmengen von nach Fakt gleich