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.
Punkte: 8.84K
\(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