c) Beweisen Sie mit kombinatorischen Überlegungen die Formel
∑k=0n(nk)=2n,n∈N \sum \limits_{k=0}^{n}\left(\begin{array}{l} n \\ k \end{array}\right)=2^{n}, \quad n \in \mathbb{N} k=0∑n(nk)=2n,n∈Nd) Zeigen Sie, dass für n,k∈N0 n, k \in \mathbb{N}_{0} n,k∈N0 mit n≥k n \geq k n≥k gilt:(n+1k)=(nk−1)+(nk) \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) (n+1k)=(nk−1)+(nk)e) Beweisen Sie die Formel aus c) durch vollständige Induktion. Verwenden Sie Aufgabenteil d).
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 2n
Zu d) :
zu e)
Ein anderes Problem?
Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos