Vollständige Induktion

25.01.2005, 22:53

Ledro

Vollständige Induktion

Hallo,

$\begin{eqnarray*} \sum_{k=1}^n~\frac{1}{5^{k-1}}= \frac{5}{4}(1-\frac{1}{5^n}) \end{eqnarray*}$ soll durch vollständige Induktion bewiesen werden.

Nach dem Induktionsanfang n=1 und dem Induktionsschritt n-1 -> n für alle n >=2 gilt:

$\begin{eqnarray*} \sum_{k=1}^n~\frac{1}{5^{k-1}}=\sum_{k=1}^{n-1}~\frac{1}{5^{k-1}}+\frac{1}{5^{n-1}}=\frac{5}{4}(1-\frac{1}{5^{n-1}})+\frac{1}{5^{n-1}} \end{eqnarray*}$
so weit ist es noch klar. aber nun verstehen ich die nächsten Schritte nicht mehr:

$\begin{eqnarray*} = \frac{5}{4}(1+\frac{4}{5}* \frac{1}{5^{n-1}}-\frac{1}{5^{n-1}}) \end{eqnarray*}$ ??? und
$\begin{eqnarray*} =\frac{5}{4}(1-\frac{1}{5}*\frac{1}{5^{n-1}}) \end{eqnarray*}$ ??? und
$\begin{eqnarray*} =\frac{5}{4}(1-\frac{1}{5^n}) \end{eqnarray*}$

Euch ganz, ganz lieben Dank für jeden Tipp!!!
ciao Ledro

25.01.2005, 23:54

JochenX

Auf diesen Beitrag antworten »

RE: Vollständige Induktion

Zitat:

Original von Ledro
Hallo,

$\begin{eqnarray*} \sum_{k=1}^n~\frac{1}{5^{k-1}}= \frac{5}{4}(1-\frac{1}{5^n}) \end{eqnarray*}$ soll durch vollständige Induktion bewiesen werden.

Nach dem Induktionsanfang n=1 und dem Induktionsschritt n-1 -> n für alle n >=2 gilt:

$\begin{eqnarray*} \sum_{k=1}^n~\frac{1}{5^{k-1}}=\sum_{k=1}^{n-1}~\frac{1}{5^{k-1}}+\frac{1}{5^{n-1}}=\frac{5}{4}(1-\frac{1}{5^{n-1}})+\frac{1}{5^{n-1}} \end{eqnarray*}$
so weit ist es noch klar. aber nun verstehen ich die nächsten Schritte nicht mehr:

was du hier machst ist einfach; ich mache mal einen zwischenschritt, dann sollte es dir klar werden:
$\begin{eqnarray*} \frac{5}{4}(1-\frac{1}{5^{n-1}})+\frac{1}{5^{n-1}}=\frac{5}{4}(1-\frac{1}{5^{n-1}})+\frac{5}{4}*\frac{4}{5}*\frac{1}{5^{n-1}} \end{eqnarray*}$
danach kannst du alles in eine gemeinsame klammer mit 5/4* davor schreiben..... damit ergibt sich das:

Zitat:

$\begin{eqnarray*} = \frac{5}{4}(1+\frac{4}{5}* \frac{1}{5^{n-1}}-\frac{1}{5^{n-1}}) \end{eqnarray*}$ ??? und

also der jetzige schritt solte klar sein! du hast 4/5 von irgendwas - 1 irgendwas=-1/5 irgendwas
damit ergibt sich das:

Zitat:

$\begin{eqnarray*} =\frac{5}{4}(1-\frac{1}{5}*\frac{1}{5^{n-1}}) \end{eqnarray*}$ ???

der letzte schritt ist klar? $\begin{eqnarray*} 5^{n-1}*5=5^{n-1+1}=5^n \end{eqnarray*}$
und damit:

Zitat:

und
$\begin{eqnarray*} =\frac{5}{4}(1-\frac{1}{5^n}) \end{eqnarray*}$

Euch ganz, ganz lieben Dank für jeden Tipp!!!
ciao Ledro

ist's dir jetzt klar? sonst frag nochmal nach!

mfg jochen

26.01.2005, 10:19

Ledro

Auf diesen Beitrag antworten »

RE: Vollständige Induktion
Jochen, die Erklärung hat mir sehr gut geholfen! wow! klasse! ganz, ganz lieben Dank!!!

Ist das Erfahrung oder wie komme ich dahin, dass ich die einzelnen Schritte mal irgendwann selbst nachvollziehen kann?!

Liebe Grüße und nochmal danke! ciao Ledro Wink

26.01.2005, 10:32

JochenX

Auf diesen Beitrag antworten »

also das nachvollziehen ist hier eigentlich nicht schwer.
du musst hier nur schauen, was sich denn geändert hat und dir dann überlegen, wie man dazu mathematisch vorgehen muss (das ist hier ja nur ausklammern, zusammenrechnen...) (genauso bin ich vorgegangen)
schwerer ist es, selbst solche lösungen zu finden.
dafür brauchst du tatsächlich etwas erfahrung.....

da hilft als tipp, nachdem du mal die induktionsannahme eingesetzt hast und nur noch den rest umformen musst, erst mal das fertige ergebnis (das herauskommen muss) hinzuschreiben.
dann kannst du dir schritt für schritt überlegen, was du alles noch umformen musst.

mfg jochen

26.01.2005, 11:23

gargyl

Auf diesen Beitrag antworten »

Der Beweis ist leider nicht richtig.

Nehmen wir an:

$\begin{eqnarray*} \sum_{k=1}^n~ \frac{1}{5^{(k-1)}} = \frac{5}{4} (1-\frac{1}{5^{n}}) \end{eqnarray*}$

Die linke Seite seie Richtig die rechte Seite seie zu beweisen.
Weiterhin seie die Gleichung für n=2 erstmalig richtig.( Zitat ....n>=2....)

Benutzen wir nun

$\begin{eqnarray*} \sum_{k=1}^n~ \frac{1}{5^{(k-1)}} = \sum_{k=1}^{n-1}~ \frac{1}{5^{(k-1)}}+\frac{1}{5^{(n-1)}}=\frac{5}{4} (1-\frac{1}{5^{n-1}}) +\frac{1}{5^{(n-1)}} \end{eqnarray*}$

Dann verwenden wir

$\begin{eqnarray*} \frac{5}{4} (1-\frac{1}{5^{n-1}}) \end{eqnarray*}$

Dieser Ausdruck wurde aber nicht als richtig erkannt.

Es muss so heissen :

$\begin{eqnarray*} \sum_{k=1}^n~ \frac{1}{5^{(k-1)}}+\sum_{k=(n+1)}^{n+1}~ \frac{1}{5^{(k-1)}} =\frac{5}{4} (1-\frac{1}{5^{n}})+ \sum_{k=(n+1)}^{n+1}~ \frac{1}{5^{(k-1)}} \end{eqnarray*}$

$\begin{eqnarray*} \sum_{k=1}^{n+1}~ \frac{1}{5^{(k-1)}}+=\frac{5}{4} (1-\frac{1}{5^{n}})+ \frac{1}{5^{n}} \end{eqnarray*}$

Die Induktion wir von n nach n+1 geführt, nicht von n-1 nach n.
Deswegen wir ja im Zweifelsfalle nachgerechnet wann eine Gleichung erstmalig stimmt.

26.01.2005, 11:34

JochenX

Auf diesen Beitrag antworten »

hmmm, lies bitte genau und rechne die formel mal für n=1 nach...
da stimmt sie und das war auch der induktionsanfang, den ledro hier nicht hingeschrieben hat (das er den richtig hat, vermute ich doch mal stark...).
also gilt für n=2: es gilt, wenn es für 2-1 gilt, da es für 2-1=1 gilt, gilt es also für n=2
für n=3 gilts, wenns für n=2 gilt... dafür gilts also auch für n=3....

und induktiv für alle natürlichen zahlen.

wo genau ist dein problem?
sicher ist das eher ungewöhnlich von n-1 auf n zu schließen, aber ich sehe da kein problem.
aber ich lasse mich gerne überzeugen, wenn die argumente stimmen.

mfg jochen

26.01.2005, 13:08

gargyl

Auf diesen Beitrag antworten »

Es gibt durchaus die Möglichkeit das eine Aussage erst ab einem bestimmten n gilt.(Vor allem bei Ungleichungen)

Geht mann dann auf n-1 zurück nimmt man Bezug auf eine Aussage die falsch ist.

Wenn man das in einer Klausur macht ist man angeschmiert.

26.01.2005, 20:19

JochenX

Auf diesen Beitrag antworten »

Zitat:

Original von gargyl
Es gibt durchaus die Möglichkeit das eine Aussage erst ab einem bestimmten n gilt.(Vor allem bei Ungleichungen)

Geht mann dann auf n-1 zurück nimmt man Bezug auf eine Aussage die falsch ist.

Wenn man das in einer Klausur macht ist man angeschmiert.

die aussage gilt immer erst ab einem entsprechenden n und wenn es n=1 ist....
und dafür zeigst du es mit dem induktionsanfang......
ich weiß immer noch nicht wo dein problem bzgl. des schlusses von n-1 nach n bei
1) diesem problem
2) einem anderen beispiel, das du mal nennen könntest
ist.

mfg jochen

27.01.2005, 08:37

klarsoweit

Auf diesen Beitrag antworten »

Ich verstehe die Bedenken von gargyl auch nicht. Der Induktionsschritt von n-1 auf n ist zwar nicht so üblich, aber ohne weiteres machbar. Es muß nur dabei beachtet werden, dass n >= 2 ist. Das hat LOED aber auch ausdrücklich erwähnt und die Bedingung ist auch nicht verletzt worden.

27.01.2005, 09:55

gargyl

Auf diesen Beitrag antworten »

Normalerweise bestimmt man das erste n für das eine Aussage gilt und schliest dan auf n+1.
Bei dem obigen Vorgehen muss man aber das erste und das zweite n für das die Aussage gilt bestimmen.

Und für diese beiden Elemente die richtigkeit zu bestiimmen bringt nicht viel.

Am Rande:

Der Induktionsbeweis müste bei n=0 beginnen.

Es fehlt jeglicher Beweis das die Gleichung überhaupt für irgend ein n stimmt.

27.01.2005, 10:21

JochenX

Auf diesen Beitrag antworten »

Zitat:

Bei dem obigen Vorgehen muss man aber das erste und das zweite n für das die Aussage gilt bestimmen.

wieso?? das es für 2 stimmt kannst du einfach daraus schließen, das es für 2-1 gilt....

Zitat:

Der Induktionsbeweis müste bei n=0 beginnen

ob 0 eine natürliche zahl ist, brauchen wir wohl kaum diskutieren....

mfg jochen

edit:
und ich deine behauptung, es fehle der beweis, dass es für eines stimmt, sind denke ich ungerechtfertigt.
aus ledros erstem text vermute ich stark, er hat es für n=1 bewiesen und hier nur nicht gepostet.
also IA gehört natürlich auf jeden fall dazu! da gebe ich dir recht!

27.01.2005, 11:02

klarsoweit

Auf diesen Beitrag antworten »

Ich versuche mal die Gemüter zu beruhigen. Schauen wir uns das Prinzip der vollständigen Induktion also nochmal an.
Wir haben eine Aussage A(n), deren Gültigkeit für alle n aus N behauptet wird.
Die vollständige Induktion besteht nun aus drei Teilen. Ja aus drei, nicht aus zwei Teilen, obwohl immer nur zwei Teile durchgeführt werden.

1. Teil: Der Induktionsanfang. Gezeigt wird die Gültigkeit der Aussage für n=1.
Also A(1) ist wahr.

2. Teil: Hier wird gezeigt: Wenn die Aussage A für eine beliebige Zahl n wahr ist, dann ist auch die Aussage A für die nachfolgende Zahl n+1 wahr.
Formal kann man auch statt n den Ausdruck k-1 verwenden und zeigt:
Für alle k >= 2: wenn A(k-1) wahr, dann ist auch A(k) wahr.
Entscheidend ist der Effekt, dass die Aussage A für die nachfolgende natürliche Zahl wahr ist, wenn die Gültigkeit für den Vorgänger bewiesen ist.

Jetzt kommt der 3. Teil, der typischerweise weggelassen wird, weil er immer gleich ist:
Wir wissen, dass die Aussage A für n=1 gilt.
Dann gilt sie aber auch für den Nachfolger, also für n=2.
Da sie nun für n=2 gilt, gilt sie auch wiederum für den Nachfolger, also für n=3.
Da auf diese Weise jede natürliche Zahl erreicht wird, ist die Gültigkeit der Aussage bewiesen. Hier ist es unerheblich, ob im 2. Teil A(n) ==> A(n+1) oder A(k-1) ==> A(k) mit k >= 2 bewiesen wurde.

Wenn das gargyl nicht überzeugt, müssen wir hier wohl eine Abstimmung unter allen Experten machen.

Noch eine Anmerkung zum Induktionsanfang: Je nach Aussage kann man auch mit n=0 oder einer negativen ganzen Zahl anfangen (solange natürlich die Aussage stimmt). Dem Induktionsbeweis ist das egal. Die Aussage gilt dann eben für alle ganzen Zahlen ab dem Induktionsanfang.

27.01.2005, 11:12

Auf diesen Beitrag antworten »

@klarsoweit

Nicht ohne Grund lässt man das, was du den dritten Teil nennst, immer weg. Da gibt es nämlich nichts zu beweisen, denn das ist das sogenannte Induktionsaxiom, ein Bestandteil der axiomatischen Definition der natürlichen Zahlen nach Peano:

http://de.wikipedia.org/wiki/Peano-Axiome

Neue Frage »

Antworten »

Vollständige Induktion

Verwandte Themen