Beweis einer Summe mit Hilfe einer anderen Aufgabe

Question

Folgende Aufgabe verstehe ich nicht:

4) Beweisen Sie mit Hilfe der obigen Aufgabe, dass \( \sum\limits_{k=0}^{n}{(n über k)} \) = 2ⁿ

Die "obige Aufgabe" lautet:

3) Wie viele k-elementige Teilmengen besitzt eine n-elementige Menge (Beweis durch vollständige Induktion).

Die Aufgabe 3 verstehe ich, nur die 4 nicht, bzw. wie ich die 3) auf die 4) anwenden soll.

Das "n über k" in der Summe soll folgendes bedeuten:

\( \begin{pmatrix} n \\ k \end{pmatrix} \)

Answer 1

Die Summe \( \sum\limits_{k=0}^{n}{(n über k)} \) läuft über alle k von 0 bis n,

also werden alle Teilmengen erfasst. Und die Anzahl aller möglichen

Teilmengen einer einer n-elementigen Menge ist 2^n.

Comments

und \( \binom{n}{k} \) ist genau die Anzahl der k-elementigen Teilmengen einer n-elementigen Menge.

---

Danke für die Antwort. Wie könnte ich das ganze denn zu Papier bringen? Genau, so wie du es geschrieben hast oder wie?

---

Ja. Das nennt sich Beweis durch doppeltes Abzählen.

https://de.wikipedia.org/wiki/Doppeltes_Abz%C3%A4hlen

Man zählt hier also die Teilmengen einer n-elementigen Menge doppelt ab.