Fibonacci, vollst. Induktion

Aufrufe: 462     Aktiv: 09.01.2021 um 14:45
0

Hallo zusammen, es geht um folgende Aufgabe:

 

Ich weiß, wie die vollständige Induktion funktioniert und beherrsche sie mit Summen- und Produktzeichen und Teilbarkeit auch. Bloß hier bin ich überfordert, weil ich nicht weiß, wie ich die kleinergleich-Beziehungen beweisen soll.

Mein Ind.anfang wäre n = 0: 0 kleinergleich f(0) = 1 kleinergleich f(0+1 = 1) = 1 kleinergleich 2^0 = 1,

also 0 kleinergleich 1 kleinergleich 1 kleinergleich 1

Mein Ind.voraussetzung ist klar:  ich schreib nochmal das hin, was da steht.

Meine Ind.behauptung wäre 0 kleinergleich f (n+1) kleinergleich f (n+2) kleinergleich 2^(n+1)

Jetzt ist mein Problem wie gesagt, dass ich nicht weiß, wie ich im Induktionsschritt vorgehen soll. Kann mir da jemand weiterhelfen?

Diese Frage melden
gefragt

Student, Punkte: 260

 
Kommentar schreiben
1 Antwort
1

Ich würde dir empfehlen zwei getrennte Induktionsbeweise zu führen.

Zunächst zeigst du \(f_n\leq f_{n+1}\). Dabei führst du einfach ganz normal deinen Induktionsbeweis, bloß dass du beim Induktionsschritt noch einmal nach oben abschätzt. Du kommst wahrscheinlich recht schnell ans Ziel, indem du die Rekursionsformel für die Fibonacci-Folge benutzt.

Danach zeigst du \(f_{n+1} \leq 2^n\). Auch hier ein ganz üblicher Induktionsbeweis mit einer geeigneter Abschätzung im Induktionsschritt.

Du kannst bei beiden Varianten (glaube ich zumindest) erst die Rekursionsformel benutzen und dann die Induktionsvoraussetzung zwei mal (für beide Zahlen der Rekusionsvorschrift) anwenden. Dann nur noch geeignet nach oben abschätzen. (Gegebenfalls erst Ausklammern, was in beiden Termen gleich ist)

Das \(0\leq f_n\) gilt, musst du denk ich nicht mit Induktion zeigen, da deine ersten beiden Glieder ja größer sind als Null und die Folge monoton wachsend ist, bleibt diese Ungleichung also auch für alle \(f_n\) erfüllt.

 

Hoffe das hilft weiter.

 

Diese Antwort melden
geantwortet

Punkte: 8.84K

 
Ehrlich gesagt überhaupt nicht, aber ich bin bei Fibonacci eh vorgeschädigt. Ich hab echt keinen Dunst, wie das aussehen würde, aber ich google mal bisschen rum, vielleicht find ich was. Danke auf jeden Fall für die schnelle und nette Antwort.   ─   akimboslice 09.01.2021 um 14:40
Schreib es einfach mal auf. z.B. würde für die zweite Ungleichung im Induktionsschritt folgendes herauskommen:
\(f_{n+2}=f_n +f_{n+1} \overset{2\times IV}{\leq} 2^{n-1} +2^n=2^{n-1} \cdot (1+2) <\ldots \)
wie müsste die Abschätzung dort jetzt weiter aussehen.   ─   maqu 09.01.2021 um 14:44

Kommentar schreiben