Zeigen sie Für alle natürlichen Zahlen n gilt: Summe von Binomialkoeffizienten ist 2^n.

Question

n
∑       (n über k) = 2^n
k=0


Leider habe ich hier keine Ahnung wie ich das hier angehe.
Setze ich für das n etwa n+1 ein?
Oder wird das so aussehen: 2^n+2^{n+1}

Comments

Vgl. auch hier: https://www.mathelounge.de/393048/binomialverteilung-zeige-summe-binomialkoeffizienten-gibt

Aber das ist ja dort deine Antwort.

Answer 1

(n über k) ist die Anzahl der k-elementigen Teilmengen einer n-elementigen Menge.

∑_k=0..n(n über k) summiert über alle möglichen k, ist also die Anzahl der Teilmengen einer n-elementigen Menge.

2ⁿ ist ebenfalls die Anzahl der Teilmengen einer n-elementigen Menge.

Also muss ∑_k=0..n(n über k) = 2ⁿ sein.

Comments

Was genau aber muss ich jetzt tun?

---

Du musst nachvollziehen, warum meine Antwort tatsächlich zeigt, dass ∑_k=0..n(n über k) = 2ⁿ für jede natürliche Zahl ist.

Answer 2

Beweis durch vollständige Induktion: Es ist zu zeigen Dass unter der Voraussetzung

n
∑       (n über k) = 2ⁿ
k=0

gilt:

n+1
∑       (n+1 über k) = 2·2ⁿ
k=0

Schreibe dafür die Summe

n+1
∑       (n+1 über k) 
k=0

in den ersten und letzten drei Gliedern auf, dazwischen Pünktchen. Nach dem Aufbau des Pascalschen Dreiecks ist jeder Summand aus S_n+1 bis auf den ersten und letzten die Summe aus zwei in der vorhergehenden Zeile stehenden Summanden von S_n. Dabei kommt  jeder Summand von S_n in S_n+1 doppelt vor bis auf den ersten und letzten von S_n. Der erste und letzte Summand heißen in jedem Falle 1 und können durcheinander ersetzt werden. Daher kommt jeder Summand aus S_n in S_n+1 doppelt vor.

Answer 3

2 = (1 + 1)