Wie kann ich die Summe aus 2^k=(2^(n+1))-1 durch vollständige Induktion und einen Widerspruch beweisen?

... komplette Frage anzeigen

2 Antworten

Hallo,

die vollständige Induktion läuft nach folgendem Schema ab:

Beweise die Behauptung für das erste Glied, hier also für k=0

Σ2^0 =2^(0+1)-1=1

Nun überlegst Du, wie Du von der Summe von 2^k auf das nächste Glied der Folge, nämlich auf die Summe von 2^(k+1) kommst. Nach den Potenzgesetzen dadurch, daß Du 2^k mit 2 multiplizierst: 2*2^k=2^(k+1) und dies zu der Summe von 2^k addierst.

Die Behauptung ist: Die Summe von 2^k, wenn Du für k alle natürlichen Zahlen von 0 bis n einsetzt und die Ergebnisse addierst, ist dasselbe, also wenn Du k für n in die Formel 2^(n+1)-1 einsetzt.

Mit dem Induktionsanfang hast Du bereits nachgewiesen, daß dies für n=0 stimmt. Wenn es auch für das jeweils folgende Glied stimmen soll, muß die Summe von 2^(k+1), also die Summe von 2^k plus 2*2^k, dasselbe sein, als wenn Du k+1 für n in die Summenformel einsetzt: 

Summe von 2^k=2^(k+1)-1

Summe von 2^(k+1)=2^(k+1)-1+2^(k+1)

Setzt Du k+1 direkt in die Summenformel ein, steht da:

2^(k+2)-1

Zu beweisen ist nun, daß 2^(k+1)-1+2^(k+1)=2^(k+2)-1

2^(k+2)=2*2^(k+1)

2^(k+1)+2^(k+1)=2*2^(k+1)

Also:

2*2^(k+1)-1=2*2^(k+1)-1

Wir sind auf zwei unterschiedlichen Wegen zum gleichen Ergebnis gekommen.

Einmal haben wir zu der Summenformel von 2^k das nächste Glied addiert, dann haben wir k+1 direkt in die Summenformel eingesetzt.

Die Summenformel stimmt also für beliebige n.

Damit wäre auch die Gegenbehauptung widerlegt, daß nämlich 2^(n+1)-1 nicht die Summe von 2^n für k=0 bis k=n darstellt.

Herzliche Grüße,

Willy

Antwort bewerten Vielen Dank für Deine Bewertung

Was GENAU sind denn deine Fragen? Aber so nebenbei: Dass ihr diese Gleichheit durch WIDERSPRUCH beweisen sollt, wage ich zu bezweifeln.

Gib bitte einmal die Aufgabe im Originalwortlaut wieder.

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von boertiii
30.10.2016, 15:36

a) Beweisen Sie die Behauptung mittels vollstandiger Induktion.
b) Beweisen Sie die Behauptung in Form eines Widerspruchsbeweises.
Tipp: Wenn es ein Gegenbeispiel gibt, so gibt es auch ein kleinstes Gegenbeispiel.

0

Was möchtest Du wissen?