Endliche Menge/Siebformel/Fakt/Beweis

Aus Wikiversity
Beweis

Wir beweisen die Aussage durch Induktion über , wobei der Fall klar ist. Für siehe Aufgabe. Es ist

wobei wir für die zweite Gleichung den Fall von zwei Teilmengen und für die dritte und die vierte Gleichung die Induktionsvoraussetzung verwendet haben. Für die fünfte Gleichung führen wir hinten die Indexverschiebung durch und der mittlere Term wird in die rechte Summe integriert. Die sechste Gleichung ergibt sich von unten nach oben gelesen, wenn man die Teilmengen

je nachdem aufspaltet, ob dazu gehört oder nicht.