Vollständige Induktion: Summe ( n über k) = 2^{n}

Question

bin gerade dabei Summe ( n über k)  = 2^n zu beweisen (per vollständiger Induktion).

Leider habe ich gerade Probleme beim umformen:

1) n! / (k! * (n - k)!) + (n + 1) = 2^{n+1}

2) n! / (k! * (n - k)!) + (n + 1) = (n + 1)! / ((n + 1) -k)! * k!)

Ab hier komme ich nicht mehr weiter.

Florian T. S.

EDIT(Lu): Wort "Summe" eingefügt. 

Comments

Vermute du meinst die Summe von k=0 bis n auf der linken Seite.

---

Exakt, also die Summe von n über k  mit (n + 1), da der nächste Schritt (A(n+1)) bewiesen werden soll :-)

---

Weiß jemand, wie man das beweist:

∑(n über k) = 2ⁿ

(Summe von k=0 bis n)

Ich hab es schon mit vollständiger Induktion versucht, aber dann erhalte ich

∑(n+1 über k) + (n+1 über k+1) und ich kann den ersten Teil nicht einfach mit 2ⁿ ersetzen.

Wie muss ich das machen?

---

Wie kann man das zeigen?

Answer 1

Du meinst 

∑ (k = 0 bis n) (COMB(n, k)) = 2^n

Sehr gut wird die Formel am Pascalschen Dreieck deutlich. 

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

In eine Zeile geht die darüber liegende Zeile immer genau 2 mal ein. Dadurch verdoppelt sich die Zeilensumme immer.

Ein anderer Weg

Comments

Danke Mathecoach! Schaue mir das Video gleich mal an :-)

Du rettest mich echt, dass ich gut vorbereitet bin :-D Danke hierfür!

---

Gast: Schau auch mal hier: https://www.mathelounge.de/61002/zeigen-sie-dass-die-folgende-gleichung-gilt-∑-n-tief-k-2-n 

---

Danke Lu!

@ Mathecoach: Ist wirklich super! Im Prinzip muss man "nur" mit dem Laufindex "rumschieben".
Ist wieder eine neue Gewöhnungssache.
Das Einzige was mir nicht geläufig ist, ist:

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

Warum 0? Da müsste doch eigentlich k stehen?

Grüße :-)

---

Ich hoffe mal du meinst den folgenden Teil. Wenn nicht, dann bitte nochmal genauer sagen was du meinst.

Man nimmt einfach die Summanden (k = 0) und (k = n + 1) aus dem Summenzeichen heraus und schreibt diese Summanden extra hin.

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

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

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

= ∑ (k = 1 bis n) (n + 1 über k) + 2

---

Alles klar jetzt kann ichs nachvollziehen. 
Vielen Dank Mathecoach :-)

Answer 2

die Frage wurde schon einmal beantwortet:

https://www.mathelounge.de/267186/vollstandige-induktion-summe-n-uber-k-2-n

Gruß Wolfgang

Answer 3

Schau mal unter 

https://www.mathelounge.de/267186/vollstandige-induktion-summe-n-uber-k-2-n

Das sollte dir eigentlich weiterhelfen.

Comments

Danke dir :) Kann ich mit "j" statt "k" die gleiche machen? Oder brauche ich noch etwas?

---

Ob du jetzt j oder k nimmst ist ja egal. Wichtig ist das du das mit der Indexverschiebung verstehst.

Darauf beruhen alle Beweisregeln mit Binomialkoeffizienten.