Binomialidentitäten verstehen

Pascal-Regel und Teilmengenstrukturen · Abschnitt 23 von 64

Beweis

Eine Menge, zwei Zählweisen

Alle Teilmengen werden direkt als $2^n$ Binärentscheidungen oder nach ihrer Größe als $\sum_{k=0}^n\binom nk$ gezählt. Daher sind beide Ausdrücke gleich.

Strategie

Identität lesen statt umformen

Suche links und rechts nach Beschreibungen derselben Objektmenge. Summen deuten auf Fälle, Produkte auf aufeinanderfolgende Entscheidungen und Binomialkoeffizienten auf Teilmengen fester Größe.

Achtung

Beispiele beweisen keine Identität

Numerische Kontrollen helfen beim Entdecken. Ein Beweis erklärt jedoch, warum die beiden Zählweisen für jedes zulässige $n$ dieselben Objekte erfassen.