Rekursive Folgen | MathePrisma

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.

Nein! Wir nehmen nicht den Aufzug!

Was hat das mit Rekursiven Folgen zu tun?

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

Hilfe:
Bewege die Maus über das Bild

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)

Tipp:
Erst "Herunterhangeln", dann "Hochhangeln"

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.

Dies entspricht genau der Fibonacci-Folge:

Fibonacci-Folge

Startwert	F(1)=1
	F(2)=1
Vorschrift	F(n)=F(n-1) + F(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) = \frac{(\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n}{\sqrt{5}} = \frac{\tau_1^n - \tau_2^n}{\sqrt{5}}$

mit $\tau_1 = \frac{1+\sqrt{5}}{2} = 1,618033...$ und $\tau_1 = \frac{1-\sqrt{5}}{2} = -0,618033...$ (Beweis)
$\tau = \tau_1 = \frac{1+\sqrt{5}}{2}$ ist dabei die Zahl des Goldenen Schnitts.

zur 1. Stufe?	zur 2. Stufe?	zur 3. Stufe?	zur 4. Stufe?	zur 5. Stufe?	zur 6. Stufe?	zur 7. Stufe?