Zeigen Sie, dass für n, k ∈ ℕ_{0} mit n ≥ k gilt:

Question

c) Beweisen Sie mit kombinatorischen Überlegungen die Formel

\( \sum \limits_{k=0}^{n}\left(\begin{array}{l} n \\ k \end{array}\right)=2^{n}, \quad n \in \mathbb{N} \)
d) Zeigen Sie, dass für \( n, k \in \mathbb{N}_{0} \) mit \( n \geq k \) gilt:
\( \left(\begin{array}{c} n+1 \\ k \end{array}\right)=\left(\begin{array}{c} n \\ k-1 \end{array}\right)+\left(\begin{array}{l} n \\ k \end{array}\right) \)
e) Beweisen Sie die Formel aus c) durch vollständige Induktion. Verwenden Sie Aufgabenteil d).

Answer 1

Zu c) man kann den Binomialkoeffizient (n,k) interpretieren als "Anzahl der k- elementigen Teilmengen einer n-elementigen Menge S. Wenn du nun die Summation über k∈[0,n] betrachtest, erhältst du die Anzahl aller Teilmengen der n-elementigen Menge S (da du die Anzahl 1-elementigen, 2-elementigen... Teilmengen von S addiert hast). Die Anzahl aller Teilmengen von S beträgt aber 2ⁿ

^{Zu d)  :}

zu e)