TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 169

Aus VoWi
Zur Navigation springen Zur Suche springen

Sei M eine nichtleere endliche Menge. Zeigen Sie: M besitzt gleich viele Teilmengen mit gerader Elementanzahl wie solche mit ungerader Elementanzahl.

Lösungsvorschlag von moritz.f

Nach der Übung am 21.Nov.2008
Die Anzahl der Teilmengen der Länge k ist \begin{pmatrix} n \\ k\end{pmatrix} Also ist die Anzahl aller Teilmengen \sum\limits_{k = 0}^n \begin{pmatrix} n \\ k\end{pmatrix}

Um jetzt nur gerade Teilmengen zu verwenden, multipliziert man (-1)^k hinein (ist positiv bei geraden, negativ bei ungeraden.)

\sum\limits_{k = 0}^n \begin{pmatrix} n \\ k\end{pmatrix} (-1)^k

Wenn die beiden Mengen gleich sind, dann muss diese Summe 0 sein.

nach Binomischem Lehrsatz ist es das gleich mit \sum\limits_{k=0}^n \begin{pmatrix}n \\ k\end{pmatrix} * 1^{(n-k)}  * (-1)^k = (1 - 1)^n, letzteres ist trivialer Weise 0