Vollständige Induktion

18.03.2009, 18:15

Hängemathe

Vollständige Induktion

Mit Hilfe von vollständiger Induktion soll gezeigt werden, dass A(n) = $\begin{eqnarray*} 1+\frac{1}{2} + \frac{1}{3} + \frac{1}{4} +...+\frac{1}{2^n} \geq 1 + n\cdot \frac{1}{2} \end{eqnarray*}$ gilt.

Also soll ich zeigen dass A(n+1) = $\begin{eqnarray*} 1+\frac{1}{2} + \frac{1}{3} + \frac{1}{4} +...+\frac{1}{2^n} + \frac{1}{2^{n+1}} \geq 1 + (n+1)\cdot \frac{1}{2} \end{eqnarray*}$ gilt.

Für 1 ist A(1) erfüllt, nun müsste ich "nur noch" den Schluss von A(n) nach A(n+1) zeigen.

Ich probiere zuerst einmal umgangssprachlich zu formulieren wie ich sonst immer (erfolgreich) vorgehe. Ich nehme die Gleichung von A(n) und addiere den Therm der bei A(n+1) dazu kommt auf beiden Seiten hinzu. Dann forme ich die rechte Seite der Gleichung oder Ungleichung so um dass ich auf das selbe komme wie bei der rechten Seite von A(n+1), und schon habe ich den Beweis vollbracht.

Konkret würde dies hier so aussehen:

$\begin{eqnarray*} 1+n\cdot \frac{1}{2}+ \frac{1}{2^{n+1}} \end{eqnarray*}$ . Nur weiß ich nicht im Ansatz wie ich auf das richtige Ergebnis kommen soll traurig

18.03.2009, 18:20

klarsoweit

Auf diesen Beitrag antworten »

RE: Vollständige Induktion

Zitat:

Original von Hängemathe
A(n+1) = $\begin{eqnarray*} 1+\frac{1}{2} + \frac{1}{3} + \frac{1}{4} +...+\frac{1}{2^n} + \frac{1}{2^{n+1}} \end{eqnarray*}$

Diese Pünktchenschreibweisen bringen nicht selten Unglück, so auch hier. Obiges ist falsch. A(n+1) sieht anders aus. Überlege mal genau.

18.03.2009, 18:29

Hängemathe

Auf diesen Beitrag antworten »

A(n+1) = $\begin{eqnarray*} 1+\frac{1}{2} + \frac{1}{3} + \frac{1}{4} +...+ \frac{1}{2^{n+1}} \geq 1 + (n+1)\cdot \frac{1}{2} \end{eqnarray*}$

?

18.03.2009, 18:38

klarsoweit

Auf diesen Beitrag antworten »

Und welche Summanden kommen bei A(n+1) im Vergleich zu A(n) noch hinzu?

18.03.2009, 18:45

Hängemathe

Auf diesen Beitrag antworten »

Ich habe schon noch mehr als diese Zeile im Kopf gehabt und auch schon ein bisschen weiter gedacht, ich gucke gleich ob ich das Problem jetzt lösen kann und poste dann nochmal ;-)

Danke schon mal für die Hilfe, ich poste dann bald mein Ergebnis.

Der zusätzliche Summan müsste $\begin{eqnarray*} \frac{1}{2^n} \end{eqnarray*}$ sein.

18.03.2009, 19:07

klarsoweit

Auf diesen Beitrag antworten »

Nein. Der ist ja schon in A(n) enthalten. Im übrigen habe ich von Summanden (Plural) geredet. Augenzwinkern

18.03.2009, 19:21

Hängemathe

Auf diesen Beitrag antworten »

Ich kann es gerade nicht mathematisch formulieren, aber es kommen die Terme dazu die zwischen $\begin{eqnarray*} \frac{1}{2^{n}} \end{eqnarray*}$ und $\begin{eqnarray*} \frac{1}{2^{n+1}} \end{eqnarray*}$ liegen ohne ersteren und inklusive letzterem.

18.03.2009, 19:50

klarsoweit

Auf diesen Beitrag antworten »

OK. Da $\begin{eqnarray*} \frac{1}{2^{n+1}} = \frac{1}{2^n + 2^n} \end{eqnarray*}$ ist, sind das genau genommen die Summanden $\begin{eqnarray*} \frac{1}{2^n+1} + \frac{1}{2^n+2} + ... + \frac{1}{2^n + 2^n} \end{eqnarray*}$ . Jeden dieser Summanden kannst du nach unten durch $\begin{eqnarray*} \frac{1}{2^{n+1}} \end{eqnarray*}$ abschätzen. Wieviel Summanden sind das insgesamt?

18.03.2009, 19:58

Hängemathe

Auf diesen Beitrag antworten »

Das wären dann $\begin{eqnarray*} 2^n \end{eqnarray*}$ Summanden, wobei ich deine Summation verstehe, irgendwie aber doch nicht ganz nachvollziehen kann. Insbesondere nach unten abschätzen sagt mir nicht viel und abschätzen klingt für mich nach einer "ungenauen" Operation. Damit will ich keinesfalls sagen dass du Unrecht hast ,denn du hast die Problematik mit Sicherheit verstanden und kannst die Aufgabe auch lösen. Ich bin immer noch irritiert.

18.03.2009, 20:06

klarsoweit

Auf diesen Beitrag antworten »

Was heißt hier "ungenaue" Operation? Eine Ungleichung (und damit haben wir es hier doch im Grunde zu tun) ist immer eine "ungenaue" Operation. Man sagt eben, daß etwas größer ist als was anderes. Das ist irgendwie ungenau, aber trotzdem mathematisch insofern exakt, als man keine falsche Aussage macht.

Wir können jetzt also folgende Abschätzung machen:

$\begin{eqnarray*} \frac{1}{2^n+1} + \frac{1}{2^n+2} + ... + \frac{1}{2^n + 2^n} \geq 2^n \cdot \frac{1}{2^{n+1}} \end{eqnarray*}$ .

Jetzt noch ein kleiner Rechenschritt und du bist fertig.

18.03.2009, 21:01

Hängemathe

Auf diesen Beitrag antworten »

Also wird auf beiden Seiten für A(n+1) $\begin{eqnarray*} 2^n \cdot \frac{1}{2^{n+1}} \end{eqnarray*}$ addiert.

Ergo sieht meine rechte Seite der Ungleichung für A (n+1) so aus:

$\begin{eqnarray*} 1+ n\frac{1}{2} + 2^n \cdot \frac{1}{2^{n+1}} \end{eqnarray*}$

$\begin{eqnarray*} 1+ n\frac{1}{2} + 2^n \cdot \frac{1}{{2^n}+2^n} \end{eqnarray*}$

$\begin{eqnarray*} 2^n \end{eqnarray*}$ kürzt sich aus dem letzten Term raus und durch Ausklammern von n+1 ist der Beweis abgeschlossen. So richtig ?

18.03.2009, 21:41

klarsoweit

Auf diesen Beitrag antworten »

RE: Vollständige Induktion
Im Prinzip ja. Allerdings habe ich mich von dir zu einer formalen Ungenauigkeit hinreißen lassen. Richtig geht das ganze so:

Es sei A(n) die Aussage: $\begin{eqnarray*} 1+\frac{1}{2} + \frac{1}{3} + \frac{1}{4} +...+\frac{1}{2^n} \geq 1 + n\cdot \frac{1}{2} \end{eqnarray*}$

Es wird behauptet, daß A(n) für alle n aus N gilt.

Induktionsanfang ist klar. Im Induktionsschritt ist zu zeigen, daß gilt:
A(n) ==> A(n+1)
d.h.:
$\begin{eqnarray*} 1+\frac{1}{2} + \frac{1}{3} + \frac{1}{4} +...+\frac{1}{2^n} \geq 1 + n\cdot \frac{1}{2} \end{eqnarray*}$
==>
$\begin{eqnarray*} 1+\frac{1}{2} + \frac{1}{3} + \frac{1}{4} +...+\frac{1}{2^n} + \frac{1}{2^n+1} + ... + \frac{1}{2^{n+1}} \geq 1 + (n+1) \cdot \frac{1}{2} \end{eqnarray*}$

In einem separaten Schritt zeigen wir: $\begin{eqnarray*} \frac{1}{2^n+1} + ... + \frac{1}{2^{n+1}} \geq 2^n \cdot \frac{1}{2^{n+1}} \end{eqnarray*}$

Dann ist:

$\begin{eqnarray*} 1+\frac{1}{2} + \frac{1}{3} + \frac{1}{4} +...+\frac{1}{2^n} + \frac{1}{2^n+1} + ... + \frac{1}{2^{n+1}} \geq 1+\frac{1}{2} + \frac{1}{3} + \frac{1}{4} +...+\frac{1}{2^n} + 2^n \cdot \frac{1}{2^{n+1}} \end{eqnarray*}$

Der Rest ist dann klar.

18.03.2009, 21:54

Hängemathe

Auf diesen Beitrag antworten »

Ok, vielen Dank für deine Hilfe. Der separate Schritt ist mir noch nicht so ganz klar, aber das muss ich mir dann selbst irgendwie vermitteln. Aber im Großen und Ganzen habe ich es verstanden, es war bisher auch die einzige Aufgabe zur vollständigen Induktion die ich nicht selbst lösen konnte.

19.03.2009, 08:21

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von Hängemathe
Der separate Schritt ist mir noch nicht so ganz klar

Wieso nicht. Gerade der ist doch am ehesten einzusehen, wenn man sich das mal am Beispiel $\begin{eqnarray*} \frac{1}{2^1 + 1} + \frac{1}{2^{1+1}} = \frac{1}{3} + \frac{1}{4} \geq \frac{1}{4} + \frac{1}{4} = 2^1 \cdot \frac{1}{2^{1+1}} \end{eqnarray*}$ ansieht.

Neue Frage »

Antworten »

Vollständige Induktion

Verwandte Themen