TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 174

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

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

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