Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Vollständige Induktion

Vollständige Induktion

Universität / Fachhochschule

Tags: Fibonacci, goldener Schnitt, Induktion

Tamen aktiv_icon

23:30 Uhr, 10.11.2016

Ich habe Probleme bei dieser Aufgabe, ich habe eine Idee bin mir aber nicht sicher ob ich das so machen darf.

Die Aufgabe lautet:

□

werde ich für den goldenen Schnitt benutzen.

Einmal sind die Fibonacci Zahlen gegeben mit:

Fibonacci Zahlen: 0,1,1,2,3,5

F_{0} = 0

F_{1} = 1

F_{n + 1} = F_{n} + F_{n - 1}

Der goldene Schnitt ist:

□ = \frac{1 + \sqrt{5}}{2}

Es soll mit vollständiger Induktion bewiesen werden, das folgende Abschätzung für alle

n € N, n \geq

2 gültig ist.

F_{n} \geq □^{n - 2}

Außerdem soll der Induktionsanfang (IA) für n=2 und n=3 gezeigt werden, da dass anscheind wichtig für die Aufgabe ist.

IA:
Ich kürze den Induktionsanfang ein wenig:
n=2

F_{2} \geq □^{0}

1 \geq 1

n=3

F_{3} \geq □^{1}

2 \geq \frac{1 + \sqrt{5}}{2}

IV lass ich jetzt weg
IB:

F_{n + 1} \geq □^{n - 1}

IBeweis:

F_{n + 1} \geq □^{n - 1}

F_{n + 1} = F_{n} + F_{n - 1} ∣ I V B e n u t z e n

\geq F_{n - 1} + □^{n - 2}

Ab hier bekomme ich meine Probleme ich habe mir überlegt, da ich ja den IA für n=2 und n=3 gemacht habe. Das man nicht nur

F_{n} \geq □^{n - 2}

benutzen darf sondern auch

F_{n - 1} \geq □^{n - 3}

einsetzen darf. Oder ist das vollkommen falsch.
Könntet ihr mir dann einen Ansatz schreiben, wie ich weiter kommen kann.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Werner-Salomon aktiv_icon

09:58 Uhr, 11.11.2016

Hallo,
Es gilt nach wie vor

F_{n} = F_{n - 1} + F_{n - 2}

Aus dem IA folgt

F_{n} \geq ψ^{n - 3} + ψ^{n - 4}

Ausklammern

F_{n} \geq ψ^{n - 4} (ψ + 1)

Kommst Du allein weiter?

Gruß Werner

Tamen aktiv_icon

16:46 Uhr, 11.11.2016

Erstmal vielen Dank für deine Hilfe.
aber ich glaube, dass ich es leider noch nicht richtig verstanden habe:

Ich werde den goldenen Schnitt als

ψ

schreiben. Bei meiner Frage hatte ich es leider nicht gefunden.

Also, wenn

F_{n} = F_{n - 1} + F_{n - 2}

und

F_{n} = ψ^{n - 3} + ψ^{n - 4} .

Ist dann auch

ψ^{n - 2} = ψ^{n - 3} + ψ^{n - 4}

?
Ich habe da irgendwie meine Zweifel.

Wenn ich jetzt deinen Ansatz Umschreibe:

F_{n + 1} \geq ψ^{n - 2} + ψ^{n - 3}

F_{n + 1} \geq ψ^{n - 3} (ψ + 1)

Wenn ich das richtig verstanden habe muss ich ja irgendwie zeigen, dass der rechte Teil kleiner ist als der linke und somit auch der rechte Teil unserer IBehauptung kleiner ist als der Linke.
Muss ich jetzt etwas auf der rechten Seite addieren oder multiplizieren um zu zeigen das die rechte kleiner ist?

z.B das ich mal

ψ

rechne?

F_{n + 1} \geq ψ^{n - 3} (ψ + 1) * ψ

F_{n + 1} \geq ψ^{n - 1} + ψ^{n - 2}

Aber jetzt ist da immer noch ein

ψ^{n - 2}

zu viel.

Bin ich schon auf dem richtigen weg oder mach ich es komplett falsch.

Werner-Salomon aktiv_icon

19:55 Uhr, 11.11.2016

Hallo Tamen,

Du schriebst: "Wenn ich das richtig verstanden habe muss ich ja irgendwie zeigen, dass der rechte Teil kleiner ist als der linke.."

Durch den IA (Induktionsanfang) hast Du doch bereist gezeigt, dass

F_{n} \geq ψ^{n - 2}

korrekt ist für

n = 2

und

n = 3

.

Wenn Du darauf aufbauend zeigen kannst, dass

F_{n} \geq ψ^{n - 2}

genau dann gilt, wenn

F_{n - 1} \geq ψ^{n - 3}

und

F_{n - 2} \geq ψ^{n - 4}

richtig ist, dann hast Du bewiesen, dass es für alle

n > 1

korrekt ist. Das ist der Induktionsschritt (IS).

Angenommen, die Annahme stimmt für

F_{2}

und

F_{3}

(siehe IA), dann muss es doch auch für

F_{4}

gelten. Und wenn es für

F_{4}

und

F_{3}

ok ist, dann gilt es auch für

F_{5}

usw. (siehe auch de.wikipedia.org/wiki/Vollst%C3%A4ndige_Induktion

D.h. aufbauend auf der Definition der Fibonaccifolge

F_{n} = F_{n - 1} + F_{n - 2}

und dem IA kann man sagen, dass

F_{n} \geq ψ^{n - 3} + ψ^{n - 4} = ψ^{n - 4} \cdot (ψ + 1)

richtig ist.

Gezeigt werden soll aber, dass für alle

n > 1

gilt, dass

F_{n} \geq ψ^{n - 2}

ist. Dafür kann man auch schreiben

F_{n} \geq ψ^{n - 4} \cdot ψ^{2}

.. sieht schon mal so ähnlich aus wie oben. Stellt sich bloß noch die Frage, wie der Zusammenhang zwischen

ψ + 1

und

ψ^{2}

ist!
Rechne beides doch mal aus!

ψ = \frac{1 + \sqrt{5}}{2}

Gruß
Werner

Tamen aktiv_icon

23:45 Uhr, 11.11.2016

Danke nochmal für deine Erklärungen.

Und wie eine Normale Induktionsvoraussetzung funktioniert weiß ich prinzipell eigentlich auch.
Wenn es für n auf n+1 gilt muss es ja auch für alle Zahlen gelten da man für n ja alles einsetzen darf.

Du hast es mir auch schon gut erklärt und ich müsste es wohl schon längst verstanden haben aber irgendwie habe ich ein Brett vorm Kopf.

Und wenn ich das richtig verstanden habe dann muss ich um bei dieser Induktion zu beweisen, dass

F_{n} \geq ψ^{n - 2}

für alle n€N | n

\geq 2

gilt zeigen,
dass

F_{n - 1} \geq ψ^{n - 3}

und

F_{n - 2} \geq ψ^{n - 4}

gilt.
(

F_{n + 1} \geq ψ^{n - 1}

und

F_{n + 2} \geq ψ^{n}

würde das aber genauso bewiesen oder nicht?)
So und wenn ich das auch noch richtig verstanden habe, dann funktioniert das so weil ich dann die Fibbonacciregel

F_{n} = F_{n - 1} + F_{n - 2}

verwenden kann.

und

ψ^{n - 4} * ψ^{2}

ist natürlich das gleiche wie

ψ^{n - 4} * (ψ + 1)

weil es aus der gleichen Zahl/Variable entstanden ist. ( Ich habe es auch nochmal nachgerechnet :-) )

Aber was bringt mir das jetzt. Ich überlege schon lange darüber wie ich jetzt weiter machen soll, aber ich sehe einfach keine Möglichkeit noch etwas umzuformen.
Wir wissen ja, dass

F_{n} = F_{n - 1} + F_{n - 2}

und mit (IV)

F_{n} \geq ψ^{n - 3} + ψ^{n - 4}

.
und

ψ^{n - 3} + ψ^{n - 4} = ψ^{n - 2}

weil

ψ^{n - 4} * ψ^{2}

und

ψ^{n - 4} * (ψ + 1)

gleich ist.
Aber ich komme einfach nicht darauf wie ich jetzt noch irgendwas beweisen soll.

Werner-Salomon aktiv_icon

16:23 Uhr, 12.11.2016

Hallo,

Du schriebst: "Aber ich komme einfach nicht darauf wie ich jetzt noch irgendwas beweisen soll."

.. ist ja auch kein Wunder, denn es ist doch schon alles bewiesen. Ich fasse noch mal zusammen. Zwischenschritte lasse ich weg - das steht alles schon weiter oben.

Es soll bewiesen werden, dass

F_{n} \geq ψ^{n - 2}

Es lässt sich leicht prüfen, dass

F_{2} \geq ψ^{0}

und

F_{3} \geq ψ^{1}

(das ist der Induktionsanfang)

es gilt

F_{n} = F_{n - 1} + F_{n - 2}

daraus und aus dem IA folgt, dass (... der Induktionsschritt)

F_{n} \geq ψ^{n - 3} + ψ^{n - 4} = ψ^{n - 4} \cdot (ψ + 1) = ψ^{n - 2}

q.e.d.

fertig, mehr ist es nicht!
Gruß
Werner

Tamen aktiv_icon

16:44 Uhr, 12.11.2016

Achso, dass war schon der Beweis und ich denke mir die ganze Zeit was ich den falsch mache.
Dann habe ich irgendwie zu kompliziert gedacht.

Und ich bedanke mich für deine Hilfe und deine Geduld. Du hast mir echt geholfen.

MfG Tamen

1335097

1334804

	Status: nicht eingeloggt	Noch nicht registriert?