Fibonacci-Folge

Die Fibonacci-Folge ist eine mathematische Folge von positiven ganzen Zahlen, den Fibonacci-Zahlen. Der Mathematiker Leonardo Fibonacci (Leonardo von Pisa) entwickelte sie, um das Wachstum einer Population von Kaninchen zu beschreiben, und publizierte sie in seinem Buch "Liber Abaci" aus dem Jahre 1202.

Inhaltsverzeichnis

1 Definition der Fibonacci-Folge

2 Modell einer Kaninchenpopulation

3 Formel von Binet

4 Näherungsformel für große n

5 Verwandtschaft mit dem Goldenen Schnitt

6 Beziehung zur Lucas-Folge

7 Das Zeckendorf-Theorem

8 Verallgemeinerung der Fibonacci-Folge

9 Literatur

10 Weblinks

Definition der Fibonacci-Folge

Die Folge ist rekursiv definiert durch:

$f 0 = 0$
$f 1 = 1$
$f n = f n - 1 + f n - 2$

Das bedeutet in Worten:

für die beiden ersten Zahlen werden die Werte Null und Eins vorgegeben
jede weitere Zahl ist die Summe ihrer beiden Vorgänger

Daraus ergibt sich die Folge zu

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, ...

Oft wird auch $f 0 = 0$ ausgelassen und die Fibonacci-Folge mit $f 1 = 1$ und $f 2 = 1$ beginnend definiert, insbesondere bei der Anwendung auf Situationen, in denen ein Anfangswert Null keinen Sinn ergibt.

Modell einer Kaninchenpopulation

Fibonacci stieß auf diese Folge bei der einfachen mathematischen Modellierung des Wachstums einer Kaninchenpopulation nach folgender Vorschrift:

Zu Beginn gibt es ein Paar neugeborener Kaninchen.
Jedes neugeborene Kaninchenpaar wirft nach 2 Monaten ein weiteres Paar.
Anschließend wirft jedes Kaninchenpaar jeden Monat ein weiteres.
Kaninchen leben ewig und haben einen unbegrenzten Lebensraum.

Jeden Monat kommt zu der Anzahl der Paare, die im letzten Monat gelebt haben, eine Anzahl von neugeborenen Paaren hinzu, die gleich der Anzahl der Paare ist, die bereits im vorletzten Monat gelebt haben, da genau diese geschlechtsreif sind und sich nun vermehren. Das entspricht aber gerade der oben angegebenen Rekursionsformel.

Formel von Binet

Die Fibonacci-Zahlen lassen sich auch direkt über eine Formel berechnen, die der französische Mathematiker Jacques-Philippe-Marie Binet 1843 angegeben hat:

$f_n=\frac{1}{\sqrt{5}}\left(a^n-b^n\right)$ mit a = $\frac{1+\sqrt{5}}{2}$ und b = $\frac{1-\sqrt{5}}{2}$

Diese Formel hat im Vergleich zur rekursiven Darstellung den Vorteil, dass zur Ermittlung einer Fibonacci-Zahl nicht sämtliche Vorgänger berechnet werden müssen.

Näherungsformel für große n

Für große Werte von n kann man in der Formel von Binet den Ausdruck bⁿ=(-0,618033989) ⁿ gegenüber dem Ausdruck aⁿ=1,618033989ⁿ vernachlässigen. Damit erhält man die Näherungsformel

$f_n \approx \frac{1}{\sqrt{5}} a^n = \frac{1}{\sqrt{5}} \cdot \left( \frac{1+\sqrt{5}}{2} \right)^n \approx 0{,}4472135955 \cdot 1{,}618033989^n$

Verwandtschaft mit dem Goldenen Schnitt

Wie von Johannes Kepler festgestellt wurde, nähert sich der Quotient zweier aufeinander folgender Fibonacci-Zahlen dem Goldenen Schnitt Φ an. Dies folgt unmittelbar aus obiger Näherungsformel für große n:

$\frac {f_{n+1}}{f_n} \approx a = \left(\frac{1+\sqrt{5}}{2}\right) = \Phi \approx 1{,}618{...}$

Φ ist eine irrationale Zahl. Es zeigt sich, dass sie in einem bestimmten Sinne die irrationalste aller Zahlen ist. Das bedeutet, dass sie sich nur schlecht durch ein Verhältnis zweier ganzer Zahlen annähern lässt, ein Umstand, der wesentlich zu ihrer Bedeutung in Kunst und Natur beiträgt. Am besten lässt sich Φ durch Quotienten zweier auf einander folgender Fibonacci-Zahlen darstellen. Diese Brüche lassen sich als Kettenbrüche schreiben:

$\frac{1}{1} = 1 \qquad \frac{2}{1} = 1+\frac{1}{1} \qquad \frac{3}{2} = 1+\frac{1}{1+ \frac{1}{1}} \qquad \frac{5}{3} = 1+\frac{1}{1+ \frac{1}{1+ \frac{1}{1}}} \qquad \frac{8}{5} = 1+\frac{1}{1+ \frac{1}{1+ \frac{1}{1+ \frac{1}{1}}}}$

Der Goldene Schnitt lässt sich daher als unendlicher Kettenbruch darstellen:

$\Phi = 1+\frac{1}{1+ \frac{1}{1+ \frac{1}{1+ \frac{1}{1+ ...}}}}$

Beziehung zur Lucas-Folge

Die Fibonacci-Folge lässt sich auch als Spezialfall der allgemeinen Lucas-Folge U_n(P,Q) mit P=1 und Q=-1 interpretieren:

$f_n=U_n(1,-1)=\frac{a^n-b^n}{a-b}$ mit a = $\frac{1+\sqrt{5}}{2}$ und b = $\frac{1-\sqrt{5}}{2}$

Wegen

$a-b = \sqrt{5}$

lässt sich dieser Ausdruck unmittelbar in die Formel von Binet umformen. Die Übereinstimmung mit der Fibonacci-Folge für P=1 und Q=-1 folgt auch direkt aus den folgenden Eigenschaften der Lucas-Folge:

$U 0 (P, Q) = 0$
$U 1 (P, Q) = 1$
$U n (P, Q) = P U n - 2 (P, Q) - Q U n - 1 (P, Q)$

Wählt man für die Anfangswerte der Fibonacci-Folge die Zahlen $f 0 = 2$ und $f 1 = 1$ , so erhält man die Lucas-Folge im engeren Sinne mit dem Bildungsgesetz $L n = a n + b n$ , die auch als Zwilling der Fibonacci-Folge bezeichnet wird.

Das Zeckendorf-Theorem

Das Zeckendorf-Theorem besagt, dass jede natürliche Zahl n größer Null eindeutig als Summe voneinander verschiedener, nicht direkt aufeinanderfolgender Fibonacci-Zahlen geschrieben werden kann. Das heißt, es gibt für jedes $n \in \mathbb{N}, n > 0$ eine eindeutige Darstellung der Form

$n = \sum_{i=1}^{k} c_i f_i, \qquad\ c_i\in \{0, 1\}\$ mit $\ \forall i : c_ic_{i+1}=0$ ,

Die entstehende Folge $(c)$ von Nullen und Einsen wird Zeckendorf-Sequenz genannt. Aus der Definition der Fibonacci-Zahlen folgt, dass keine zwei Einsen in einer Zeckendorf-Sequenz hintereinander stehen können.

Verallgemeinerung der Fibonacci-Folge

Ausgehend von der Formel von Binet:

$f_n=\frac{1}{\sqrt{x}}(a^n-b^n)$ mit a = $\frac{1+\sqrt{x}}{2}$ und b = $\frac{1-\sqrt{x}}{2}$

ist die Fibonacci-Folge mit x = 5 ein Spezialfall. Allgemein läßt sich eine allgemeine rekursive Formel bilden, die auch für die Fibonacci-Folge gilt:

$a_{n+1} = a_n - \frac{1-x}4\cdot a_{n-1}.$

Literatur

Hans Magnus Enzensberger, Der Zahlenteufel, ISBN 3-446-18900-9
John H. Conway und Richard K. Guy, The Book of Numbers, ISBN 0-387-97993-X
Paolo Ribenboim, The new Book of Primenumber Records, ISBN 0-387-94457-5