drei Beweise zur Fibonacci-Folge

Neue Frage »

Mathedepp Auf diesen Beitrag antworten »
drei Beweise zur Fibonacci-Folge
N´Abend,
ich hoffe ich bin hier mit meinem Problem richtig.

Die Fibonacci-Folge (f_n) sei rekursiv definiert durch (f_0)=0, (f_1)=1 und (f_n+1)=(f_n)+(f_n-1) für alle n Element IN vereinigt mit {0}.

1. Ich soll beweisen, daß für n>=5 gilt: (f_n)>=n.

2. Ich soll beweisen bzw. widerlegen, daß wenn n durch 3 teilbar ist, (f_n) gerade ist.

3. Ich soll beweisen bzw. widerlegen, daß wenn n nicht durch 3 teilbar ist, (f_n) ungerade ist.

Das ganze soll ohne die explizite Formel der Fibonacci-Folge gehen, aber ich habe beim besten Willen keinen Schimmer wie das klappen soll. Ich sitze schon seit ein paar Stunden davor und komme zu nichts Sinnvollem. Kann mir jemand helfen?
SirJective Auf diesen Beitrag antworten »
RE: drei Beweise zur Fibonacci-Folge
Bei Aufgabe 2 und 3 würde es dir sehr helfen, wenn du modulo 2 rechnen würdest. Kannst du das?

Aufgabe 1 ist ein einfacher Induktionsbeweis: Der Induktionsanfang ist die (noch von dir zu zeigende) Aussage f_5 >= 5 und f_6 >= 6.
Mathedepp Auf diesen Beitrag antworten »
RE: drei Beweise zur Fibonacci-Folge
Also von modulo 2 habe ich ehrlich gesagt noch nie etwas gehört.
mathemaduenn Auf diesen Beitrag antworten »

Hallo mathedepp,
Aufgabe 2,3 kannst Du auch mittels Induktion lösen indem du 3 aufeinanderfolgende Zahlen als ein Induktionsschritt auffässt.
gruß
mathemaduenn
SirJective Auf diesen Beitrag antworten »

Es geht auch ohne. Du musst nur unterscheiden, ob die Zahlen gerade oder ungerade sind, und beachten, dass die Summe von zwei geraden Zahlen und die Summe von zwei ungeraden Zahlen jeweils gerade ist, aber die Summe einer geraden und einer ungeraden Zahl ungerade ist. Das kannst du in einem Induktionsbeweis anwenden:

f_0 gerade
f_1 ungerade
f_2 ungerade (g+u)
f_3 gerade (u+u)
f_4 ungerade (u+g)
...
Im Induktionsschritt musst du unterscheiden, ob n durch 3 teilbar ist oder bei Division durch 3 den Rest 1 oder den Rest 2 lässt (das ist übrigens Rechnen modulo 3).

Siehe auch Kongruenz.
Mathedepp Auf diesen Beitrag antworten »
drei Beweise zur Fibonacci-Folge
Ok, ich glaube, ich kapiers langsam.
Danke erstmal für eure Denkanstöße.
 
 
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »