Zur MathePrisma-Startseite
Zur Modul-Startseite  


Rekursive Folgen (Fibonacci-Zahlen 1 )
 

 
 
Zunächst das Problem:
Wir stehen vor einer Treppe mit vielen Stufen.
Die erste Stufe muss in jedem Fall betreten werden.
Danach steht es einem frei, ob man die nächste oder die übernächste Stufe betritt.

Aufgabe

 

Nein!
Wir nehmen nicht den Aufzug!
Angenommen der Mann steht auf der 6. Stufe,
auf wieviele Arten kann er dann dorthin gelangt sein?



Java-Applet nicht darstellbar
 
Was hat das mit Rekursiven Folgen zu tun?

 

 

 

Hilfe:
Bewege die Maus über das Bild

Wenn man auf der 6. Stufe steht, ist man dorthin entweder über die fünfte oder über die vierte Stufe gelangt.

Anzahl der Wege, die zur 6. Stufe führen  =  Anzahl der Wege, die zur 5. Stufe führen  +  Anzahl der Wege, die zur 4. Stufe führen

kurz:

F(6)=F(5)+F(4)

Fragen

 

Tipp: Erst "Herunterhangeln", dann "Hochhangeln"
Wie viele Möglichkeiten gibt es also, um zu folgenden Stufen zu gelangen?
zur 7. Stufe?
zur 6. Stufe?
zur 5. Stufe?
zur 4. Stufe?
zur 3. Stufe?
zur 2. Stufe?
zur 1. Stufe?

 
formale Lösung
Startwert:
F(1)=1Wir wissen, für die erste Stufe gibt es nur eine Möglichkeit, diese zu betreten.
F(2)=1Da man die erste Stufe begehen muss, gelangt man auf die zweite durch nur noch einen Schritt.
Rekursion:(für n=3,4,5,6,...)
F(3):Zur 3. Stufe kommt man über die 2. oder 1. Stufe.
F(4):Zur 4. Stufe kommt man über die 3. oder 2. Stufe.
......
allgemein:
F(n+2):Zur (n+2)-ten Stufe kommt man über die (n+1)-te oder n-te Stufe.

Dies entspricht genau der Fibonacci-Folge:

 
Fibonacci-Folge
StartwertF(1)= 1 
 F(2)= 1 
VorschriftF(n)=F(n-1)+F(n-2)   für n>2

"anschaulich"

Man erweitert die Zahlenfolge durch Addition der letzten beiden Folgenlieder:

Auch die Fibonacci-Folge hat eine explizite Darstellung :
explizite Darstellung
F(n) = 
mit    und     (Beweis)
ist dabei die Zahl des Goldene Schnitts.

 
 
Seite 8/9