MathePrisma, Rekursive Folgen


		Rekursive Folgen (Fibonacci-Zahlen¹)

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?

formale Lösung

Startwert:
F(1)=1	Wir wissen, für die erste Stufe gibt es nur eine Möglichkeit, diese zu betreten.
F(2)=1	Da 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.