Die Fibonacci-Zahlen 1,1,2,3,5,. . . werden rekursiv definiert durch a0 := 1, a1 := 1 und an+1 := an+an−1 für n ≥ 1.

Question

Aufgabe: Die Fibonacci-Zahlen 1,1,2,3,5,. . . werden rekursiv definiert durch
a₀ := 1, a₁ := 1 und a_n+1 := a_n+a_n−1 für n ≥ 1. Zeigen Sie mit vollständiger
Induktion, dass 1 ≤ a_n+1/a_n  ≤ 2 für n ≥ 0.

Problem/Ansatz: Ich verstehe normalerweise das Prinzip der Induktion, jedoch habe ich bei dieser Aufgabe keine Ahnung, wie ich sie lösen soll, da hier als Ziel ein Intervall vorhanden ist. Das hatten wir nie im Unterricht und ich weiß nicht, wie ich das jetzt formal beweisen soll. Klar kann ich einfach für das n die zahlen einsetzen und bei immer größer werdenden Zahlen gucken, ob das Ergebnis noch im Intervall liegt. Aber das soll glaube ich nicht so gemacht werden. Ich bin dankbar für jede Hilfe.

Answer 1

Induktionschritt:

0<a_n<a_n+1 und nach Division durch a_n+1: 0<\( \frac{a_n}{a_{n+1}} \)<1 und nach Addition von 1:

1<\( \frac{a_{n+1}+a_n}{a_{n+1}} \)<2. Definition der Fibonacci-Zahlen: 1<\( \frac{a_{n+2}}{a_{n+1}} \)<2.    

Answer 2

Hallo

einfach für 2 der erste Zahlen zeigen, dann wenn 1<=a_n/a_n-1<=2

folgt 1<=a_n+1/a_n<=2

einfach indem du a_n+1=a_n+a_n-1 hinschreibst, durch a_n dividierst und dann das Ergebnis abschätzt mit der Induktionsvors.

Gruß lul

Comments

okay, ich setze einfach zB n=1 ein, wobei 2 rauskommt und bei n=2 kommt 1,5 raus. Beide liegen im Intervall. Dann verstehe ich auch warum 1<=a_n+1/a_n<=2 folgt. Das ist ja nun die Induktionsbehauptung bzw Annahme. Aber ich verstehe den Induktionsschritt leider immernoch nicht. Kannst du den bitte einmal formulieren. Ich verstehe halt nicht wie ich diese Divison und dieses Abschätzen, was du meintest, formulieren soll.

Lg und vielen dank