0 Daumen
24,7k Aufrufe



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. 

Avatar von

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) = 2n

(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 2n ersetzen.

Wie muss ich das machen?


Bild Mathematik

Wie kann man das zeigen?

3 Antworten

+1 Daumen
 
Beste Antwort

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


Avatar von 477 k 🚀

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

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

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 :-)
0 Daumen

die Frage wurde schon einmal beantwortet:

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


Gruß Wolfgang

Avatar von 86 k 🚀
0 Daumen

Schau mal unter

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

Das sollte dir eigentlich weiterhelfen.

Avatar von 477 k 🚀

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.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community