Vollständige Induktion

30.10.2009, 17:07

Bobbie

Vollständige Induktion

Hallo,

ich hab bisher kaum erfahrung mit Induktion daher bräuchte ich etwas Hilfe bei der Aufgabe.

Vorallem verwirrt mich auch das ich da praktisch zwei gleichungen / ungleichugnen hab. Deshalb hab ich etwas probleme wie ich da ran gehen soll.

Induktionsanfang wäre die Feststellung das es für n = 0 gilt.
Der Induktionsschritt wäre dann ja das ganze für n+1 zu zeigen also kann ich auf der Linken Seite der ungleichung die gleichung für Kn+1 einsetzen nur wie gehts dann weiter? Ich kann ja schlecht rechts dann eifnach n+1 hinschreiben.

Vielen Dank schonmal

31.10.2009, 15:23

kiste

Auf diesen Beitrag antworten »

Hallo,

das ist eine recht schwere Aufgabe für einen Studienanfänger.
Das Problem ist das man im Induktionsschritt nicht durchkommt mit der Behauptung $\begin{eqnarray*} K_n \geq n \end{eqnarray*}$

Beweise stattdessen induktiv $\begin{eqnarray*} K_n \geq n + 1 \end{eqnarray*}$ .

Induktionsanfang ist ja klar,
Induktionschritt dann eben $\begin{eqnarray*} K_{n+1} = 1 + \min\{2K_{\lfloor \frac n 2\rfloor},3K_{\lfloor \frac n 3\rfloor}\} \geq ... \end{eqnarray*}$
Und dort die Induktionsvorraussetzung einsetzen

31.10.2009, 16:18

Bobbie

Auf diesen Beitrag antworten »

Zitat:

Original von kiste
Induktionsanfang ist ja klar,
Induktionschritt dann eben $\begin{eqnarray*} K_{n+1} = 1 + \min\{2K_{\lfloor \frac n 2\rfloor},3K_{\lfloor \frac n 3\rfloor}\} \geq ... \end{eqnarray*}$

Das hatte ich ja auch schon smile

bzw ich war soweit:
$\begin{eqnarray*} K_{n+1} = 1 + \min\{2K_{\lfloor \frac n 2\rfloor},3K_{\lfloor \frac n 3\rfloor}\} \geq n+1 \end{eqnarray*}$

nur das is ja eher das was am ende Dastehen soll bzw der Induktionsschluss

Zitat:

Und dort die Induktionsvorraussetzung einsetzen

Ich dachte induktionsvorraussetzung = $\begin{eqnarray*} K_{n+1} = 1 + \min\{2K_{\lfloor \frac n 2\rfloor},3K_{\lfloor \frac n 3\rfloor}\} \end{eqnarray*}$
? Weil das kann ich ja schlecht da einsetzen

Noch was allgemeines zur Induktion wenn eine gleichung gegeben ist die für n+1 golt, ist es dann auch zulässig von da ausgehend zu beweisen das sie für n gilt oder ist das dann am Ziel vorbei (weil normal wäre dann die induktion ja zu zeigen , dass es für n+2 gilt)?

31.10.2009, 16:34

kiste

Auf diesen Beitrag antworten »

Zitat:

Original von Bobbie
Ich dachte induktionsvorraussetzung = $\begin{eqnarray*} K_{n+1} = 1 + \min\{2K_{\lfloor \frac n 2\rfloor},3K_{\lfloor \frac n 3\rfloor}\} \end{eqnarray*}$

Nein. Das ist nur die Definition der Folge K_n.
Die Induktionsvorraussetzung ist:
$\begin{eqnarray*} K_i \geq i + 1 \end{eqnarray*}$ für $\begin{eqnarray*} i \leq n \end{eqnarray*}$ .
Zeigen wollen wir $\begin{eqnarray*} K_{n+1} \geq n+2 \end{eqnarray*}$ (siehe auch meinem ersten Post warum).
Benutze die Vorrausetzung eben insbesondere für $\begin{eqnarray*} i = \lfloor \frac n 2\rfloor, \lfloor \frac n 3\rfloor \end{eqnarray*}$

Zitat:

Noch was allgemeines zur Induktion wenn eine gleichung gegeben ist die für n+1 golt, ist es dann auch zulässig von da ausgehend zu beweisen das sie für n gilt oder ist das dann am Ziel vorbei (weil normal wäre dann die induktion ja zu zeigen , dass es für n+2 gilt)?

Es könnte sein das man das manchmal braucht, aber das ist eine Induktion die du wohl nie benutzen wirst.
Also in deinem Fall immer auf die nächste Zahl, in deinem Beispiel also auf n+2

Neue Frage »

Antworten »

Vollständige Induktion

Verwandte Themen