vollständige induktion

16.11.2008, 11:45

Ichich

vollständige induktion

Hallo
Folgendes Problem das mich wirklich verzweifeln lässt
Zeigen Sie durch vollständige Induktion:
2^n-1 = 2^0+ 2^1+ 2^2+....+ 2^n-1

Ich hänge schon am Induktionsanfang fest. ich habe für n=1 eingesetzt:
2^1 -1 = 2^0 + 2^n-1
1= 1
Stimmt das? Wenn nicht bitte verbessert mich und helft mir bei dem Induktionsschritt
Vielen DAnk

16.11.2008, 12:21

Zizou66

Auf diesen Beitrag antworten »

Ich schreibs zuerst mal etwas schöner mit dem Formeleditor hin:

Zeigen sie:

$\begin{eqnarray*} 2^{n-1}=\sum_{k=0}^{n-1} 2^k \end{eqnarray*}$

Beim Induktionsanfang gehst du richtig vor, einfach für n=1 einsetzen, dann steht dort:

$\begin{eqnarray*} 2^{1-1}=\sum_{k=0}^{1-1} 2^k \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow 1=1 (w) \end{eqnarray*}$

So was ist nun Induktionsvoraussetzung? Und welche Ansätze hast du für den Induktionsschluss?

16.11.2008, 12:59

Ichich

Auf diesen Beitrag antworten »

OK. Danke so schön kann ich es nicht Augenzwinkern

Mit der Induktionsvoraussetzungen hab ich so meine Probleme da wir immer direkt zum Schluss übergegangen sind. Deshalb stehe ich da auf dem Schlauch
Für den Schluss habe ich folgendes:
n+1

2^n+1 -1
2+2^n -1 =2^n+2^n -1

dann verliessen sie mich auch schon!

16.11.2008, 13:13

Zizou66

Auf diesen Beitrag antworten »

Die Induktionsvoraussetzung ist: $\begin{eqnarray*} 2^{n-1}=\sum_{k=0}^{n-1} 2^k \end{eqnarray*}$
Sie besagt, dass die Gleichung für ein fest gewähltes n gilt. Um zu zeigen, dass sie für alle n gilt, musst du noch zeigen, dass sie für den Nachfolger von n gilt.

Also der Induktionsschluss sieht ja so aus:

$\begin{eqnarray*} 2^{n+1-1}=\sum_{k=0}^{n+1-1} ~ 2^k \end{eqnarray*}$

$\begin{eqnarray*} \Leftrightarrow 2^n=\sum_{k=0}^n ~ 2^k \end{eqnarray*}$

Das kann man widerrum umformen zu:

$\begin{eqnarray*} 2\cdot 2^{n-1}=\sum_{k=0}^{n-1} 2^k +2^n \end{eqnarray*}$

So nun kannst du die Induktionsvoraussetzung anwenden, probiers mal...

16.11.2008, 13:45

Ichich

Auf diesen Beitrag antworten »

Jetzt hab ich es! konnte auch alles nachvollziehen. Wenn ich aber in die umgeformte Schreibweise bsp. für n eine 1 einsetze dann funktioniert das nicht. HAb ich mich irgendwo vertan. Bis dahin ist mir alles klar

18.11.2008, 09:46

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von Zizou66
Zeigen sie:

$\begin{eqnarray*} 2^{n-1}=\sum_{k=0}^{n-1} 2^k \end{eqnarray*}$

Es ist leicht einzusehen, daß das falsch ist, da ja schon der letzte Summand der Summe $\begin{eqnarray*} 2^{n-1} \end{eqnarray*}$ ist. Richtig ist:

$\begin{eqnarray*} \sum_{k=0}^{n-1} 2^k = 2^n - 1 \end{eqnarray*}$

@Zizou66: ich bin wirklich enttäuscht. unglücklich

18.11.2008, 15:38

Zizou66

Auf diesen Beitrag antworten »

Sorry, das war mein Fehler. Ich wollte das aus IchIchs erstem Beitrag abschreiben, habe dabei wohl nicht genug aufgepasst.

Neue Frage »

Antworten »

vollständige induktion

Verwandte Themen