+1 Daumen
1,4k Aufrufe

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}

Avatar von

3 Antworten

+1 Daumen

(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.

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

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

Avatar von 107 k 🚀

Was genau aber muss ich jetzt tun?

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

0 Daumen

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

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

gilt:

n+1
∑       (n+1 über k) = 2·2n
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 Sn+1 bis auf den ersten und letzten die Summe aus zwei in der vorhergehenden Zeile stehenden Summanden von Sn. Dabei kommt  jeder Summand von Sn in Sn+1 doppelt vor bis auf den ersten und letzten von Sn. Der erste und letzte Summand heißen in jedem Falle 1 und können durcheinander ersetzt werden. Daher kommt jeder Summand aus Sn in Sn+1 doppelt vor.

Avatar von 123 k 🚀
0 Daumen

2 = (1 + 1)            

Avatar von 26 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community