Fibonacci

Eine allgemeine Formel für F_n. (Ein combinatorisches Verfahren)


Ich will wieder (wie in der Einführung) einen steinernen Pfad bauen. Der Pfad ist n dm (Dezimeter) lang und 1 dm breit. Ich verfüge über 2 Arten Steine, nämlich Steine von 1 dm x 1 dm und Steine von 1 dm x 2 dm. Wir wählen einstweilen n=8.
Sieh hier ein Beispiel eines Pfades der Länge 8 mit vier 1x1-Steinen und zwei 1x2-Steinen.


Während des Baus des Pfades wählen wir jedes Mal einen 1x1-Stein mit Wahrscheinlichkeit p, und einen 1x2-Stein mit Wahrscheinlichkeit q (=1-p). Wenn q = p², dann hat jeder Pfad der Länge 8 dieselbe Wahscheinlichkeit gebaut zu werden, nämlich p⁸ !.
Es gibt, wie wir schon aus der Einführung wissen, F₉ Möglichkeiten um einen Pfad der Länge 8 zu bauen. Also ist die Wahrscheinlichkeit dass ein Pfad der Länge 8 entsteht: F₉ p⁸.
Wenn nicht ein Pfad der Länge 8 entsteht, dann ist ein Pfad der Länge 7 gebaut worden, gefolgt von einem Stein der Länge 2. Die Anzahl solcher Pfade ist F₈, also ist die Wahrscheinlichkeit dass kein Pfad der Länge 8 entsteht F₈ p⁹.
Wir können nun folgern dass F₉ p⁸ + F₈ p⁹ = 1, und im Allgemeinen
F_n+1 pⁿ + F_n pⁿ⁺¹ = 1 mit p + p² = 1 (oder p = (5 - 1)/2 ).
Also F_n+1 = p^-n - F_n p = p^-n - p^-n+2 + F_n-1 p² = ... = p^-n (1 + (-p²) + (-p²)² + (-p²)³ + ... + (-p²)ⁿ) =
p^-n-1 ((-p²)ⁿ⁺¹ - 1) / (1 - 1/p) = (rⁿ⁺¹-sⁿ⁺¹)/(r-s) mit r = (1 + 5)/2 und s = (1 - 5)/2