Induktion abgeschlossen?

19.09.2005, 16:51

kekso

Induktion abgeschlossen?

Hallo, ich will folgende Formel über Induktion beweisen:
$\begin{eqnarray*} \sum_{i=a}^{a+n} 2^{i} = 2^{n+1} * 2^{a} - 2^{a} = 2^{a+n+1} - 2^{a} \end{eqnarray*}$

habe den ersten Induktionsschritt mit n=0 ausgeführt:

$\begin{eqnarray*} \sum_{i=a}^{a} 2^{i} = 2^{1} * 2^{a} - 2^{a} = 2^{a} \end{eqnarray*}$

und danach mit n=n+1 weitergemacht:

$\begin{eqnarray*} \sum_{i=a}^{a+1} 2^{i} = 2^{2} * 2^{a} - 2^{a} = 2^{a} + 2^{a} + 2^{a} = 2^{a} + 2^{a+1} \end{eqnarray*}$

jetzt zu meiner Frage:
Ist der Beweis damit beendet? oder bin ich total auf dem Holzweg?

Vielen Dank schon mal im Voraus

19.09.2005, 17:00

brunsi

Auf diesen Beitrag antworten »

RE: Induktion abgeschlossen?
kann mich ja irren, aber müsstes nicht in der zweiten zeile rechts vom letzen gleichheitszeichen anstatt $\begin{eqnarray*} 2^{\alpha} \end{eqnarray*}$ eher $\begin{eqnarray*} 2^1 \end{eqnarray*}$ stehen?

kenne mich da auch zwar noch nciht so ganz aus, aber ich nehme mal an, dass es so sein muss?!!

19.09.2005, 17:17

kekso

Auf diesen Beitrag antworten »

RE: Induktion abgeschlossen?
Hmm ich weis nicht genau wo du meinst.

wenn du diese zeile meinst, dann nicht:

$\begin{eqnarray*} \sum_{i=a}^{a} 2^{i} = 2^{1} * 2^{a} - 2^{a} = 2^{a} \end{eqnarray*}$
denn
$\begin{eqnarray*} \sum_{i=a}^{a} 2^{i} = (2^{1} * 2^{a}) - 2^{a} = (2^{a} + 2^{a}) - 2^{a} = 2^{a} \end{eqnarray*}$

oder ich find den fehler nicht den du meinst

19.09.2005, 18:33

brunsi

Auf diesen Beitrag antworten »

RE: Induktion abgeschlossen?
kannst du mir denn erklären, wie du auf den klammerausdruck gekommen bist (2.Post)??

denn ich verstehe das gerade überhaupt nicht. hab das lange nicht mehr gemacht udn weiß nicht mehr so recht wie man drauf kommt.

edit: was steht denn nach dem Induktionsschritt hinter dem sigma (also links vom 1.gleichheitszeichen)?

19.09.2005, 18:44

kekso

Auf diesen Beitrag antworten »

RE: Induktion abgeschlossen?
Also

$\begin{eqnarray*} 2^{1} \end{eqnarray*}$ ist ja nichts anderes als 2 deswegen kann man auch
$\begin{eqnarray*} 2 * 2^{a} \end{eqnarray*}$ oder $\begin{eqnarray*} (2^{a} + 2^{a}) \end{eqnarray*}$ schreiben.

links vom ersten gleichheitszeichen steht meiner meinung die Summe,
also $\begin{eqnarray*} 2^{a} \end{eqnarray*}$

19.09.2005, 18:47

riwe

Auf diesen Beitrag antworten »

RE: Induktion abgeschlossen?

Zitat:

Original von kekso
und danach mit n=n+1 weitergemacht:

$\begin{eqnarray*} \sum_{i=a}^{a+1} 2^{i} = 2^{2} * 2^{a} - 2^{a} = 2^{a} + 2^{a} + 2^{a} = 2^{a} + 2^{a+1} \end{eqnarray*}$

jetzt zu meiner Frage:
Ist der Beweis damit beendet? oder bin ich total auf dem Holzweg?

da ist der hund begraben!
wo ist der schluß von n auf n+1?, wo ist n?

es sollte ja dann herauskommen:
$\begin{eqnarray*} 2^{a}(2^{(n+1)+1}) \end{eqnarray*}$
werner

19.09.2005, 19:04

brunsi

Auf diesen Beitrag antworten »

RE: Induktion abgeschlossen?
ok, soweit habe ich es verstanden.

jetzt noch ne andere frage:

kann mir jemand ein gutes skript geben, wo die vollständige Induktion erklärt wird? so für dummies wie mich Big Laugh

??

wäre auch dankbar, wenn ihr dann ncoh eins über die deduktion habt.

19.09.2005, 19:12

kekso

Auf diesen Beitrag antworten »

RE: Induktion abgeschlossen?
Also ein Skript kann ich dir nicht anbieten nur den Verweis auf wikipedia, da ist eigentlich alles recht gut erklärt. Ansonsten ist ne Analysis Vorlesung zu empfehlen.

Leider hält so ein Wissen doch nicht wirklich sehr lange, hab das letzte mal vor 3 Jahren Beweise per Induktion durchgeführt.

Ich mach jetzt erstmal Feierabend und beschäftige mich morgen nochmal damit.

Danke @wernerrin für den Hinweis - werde ihm nachgehen. (ist n nicht 0 ??)

Gruß kekso

19.09.2005, 19:24

babelfish

Auf diesen Beitrag antworten »

RE: Induktion abgeschlossen?

Zitat:

Original von brunsi
kann mir jemand ein gutes skript geben, wo die vollständige Induktion erklärt wird? so für dummies wie mich Big Laugh

schau mal in unsre workshops... find ich sehr anschaulich! smile

19.09.2005, 19:35

brunsi

Auf diesen Beitrag antworten »

RE: Induktion abgeschlossen?
den habe ich mir ganz bewusst nicht angeschaut, weil ich daraus nicht schlau werde. ich will nen skript haben.

bin halt skriptfanatiker Big Laugh

20.09.2005, 09:58

kekso

Auf diesen Beitrag antworten »

Hab nochmal ne nacht drüber geschlafen und die Formel ein klein wenig abgeändert.
$\begin{eqnarray*} \sum_{i=a}^n~2^{i} = 2^{n+1} - 2^{a} , ( a,n\in \mathbb N) , n\geq a \end{eqnarray*}$

dann erster Induktionsschritt n=a
$\begin{eqnarray*} \sum_{i=a}^n~2^{i} = 2^{a} = 2^{a+1} - 2^{a} = 2* 2^{a} - 2^{a} = 2^{a} \end{eqnarray*}$

anschleißend n = n+1:
$\begin{eqnarray*} \sum_{i=a}^{n+1}~2^{i} = (\sum_{i=a}^n~2^{i}) + 2^{n+1} = 2^{n+1} - 2^{a} + 2^{n+1} = 2*2^{n+1} - 2^{a} = 2^{(n+1)+1} - 2^{a} \end{eqnarray*}$

ich glaub damit ist die ganze sache bewiesen.

20.09.2005, 11:15

JochenX

Auf diesen Beitrag antworten »

Zitat:

anschleißend n = n+1:

wenn du dir aber für diesen mathematischen unfug noch eine andere formulierung einfallen lässt
das ist PROGRAMMIERSPRACHE, nämlich eine neue zuweisung
aber in der mathematik funzt das anders, da ist die aussage (i.A.) FALSCH

schreibe lieber:
Induktionsvorausstzung: gelte nun für n aus IN: ................................... [explizit noch mal die annahme für n hinschreiben]
Induktionschritt: n -> n+1:
.......

20.09.2005, 11:34

kekso

Auf diesen Beitrag antworten »

Erstens ist es nicht teil der Frage gewesen ob das hier mathematischer Unsinn ist.
Zweitens hast du Recht es ist eine informatische Problemlösung.
Drittens geht es um die Berechnung einer Bitmaske und ist somit kein mathematischer Unfug (liegt aber meist im Auge des Betrachters).
Viertens ging es nicht um die 100%tige Ausformulierung des Beweises, wichtig war mir eher die Korrektheit der Formel.

Trotzdem Danke für den Hinweis. Der Beweis in Reinform:

Es wird behauptet, dass für alle $\begin{eqnarray*} a,n\in \mathbb N, n\geq a \end{eqnarray*}$ gültig ist :
$\begin{eqnarray*} \sum\limits_{i=a}^n~2^{i} = 2^{a} + 2^{a+1} + 2^{a+2} + ... + 2^{n} = 2^{n+1} - 2^{a} \end{eqnarray*}$

Induktionsanfang: Für n = a gilt
$\begin{eqnarray*} \sum\limits_{i=a}^a~2^{i} = 2^{a} = 2^{a+1} - 2^{a} = 2* 2^{a} - 2^{a} = 2^{a} \end{eqnarray*}$
d.h. die Behauptung ist wahr für n = a.

Induktionsschritt von n auf n+1: Unter der Annahme, dass die Aussage
$\begin{eqnarray*} \sum\limits_{i=a}^n~2^{i} = 2^{n+1} - 2^{a} \end{eqnarray*}$
wahr ist, wird die Summe für n+1 berechnet:

$\begin{eqnarray*} \sum\limits_{i=a}^{n+1}~2^{i} = (\sum\limits_{i=a}^n~2^{i}) + 2^{n+1} = 2^{n+1} - 2^{a} + 2^{n+1} = 2*2^{n+1} - 2^{a} = 2^{(n+1)+1} - 2^{a} \end{eqnarray*}$

$\begin{eqnarray*} \hookrightarrow \end{eqnarray*}$ q.e.d.

20.09.2005, 11:55

JochenX

Auf diesen Beitrag antworten »

Zitat:

Original von kekso
Induktionsanfang: Für n = a gilt
$\begin{eqnarray*} \sum\limits_{i=a}^a~2^{i} = 2^{a} = 2^{a+1} - 2^{a} \end{eqnarray*}$

hier ist dein induktionsanfang fertig...., denn hier steht ja schon die behauptung, die du zeigen solltest

so ist es besser formuliert und, wenn ich keine kleinigkeit mehr übersehen habe, richtig Freude

Neue Frage »

Antworten »

Induktion abgeschlossen?

Verwandte Themen