Solidarität

Kachelmuster aus Quadraten, deren Kantenlängen der Fibonacci-Folge entsprechen

Die Fibonacci-Folge ist die unendliche Folge von natürlichen Zahlen, die (ursprünglich) mit zweimal der Zahl 1 beginnt oder (häufig, in moderner Schreibweise) zusätzlich mit einer führenden Zahl 0 versehen ist. Im Anschluss ergibt jeweils die Summe zweier aufeinanderfolgender Zahlen die unmittelbar danach folgende Zahl:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

Die darin enthaltenen Zahlen heißen Fibonacci-Zahlen. Benannt ist die Folge nach Leonardo Fibonacci, der damit im Jahr 1202 das Wachstum einer Kaninchenpopulation beschrieb. Die Folge war aber schon in der Antike sowohl den Griechen als auch den Indern bekannt.

Weitere Untersuchungen zeigten, dass die Fibonacci-Folge auch noch zahlreiche andere Wachstumsvorgänge der Pflanzen beschreibt. Es scheint, als sei sie eine Art Wachstumsmuster in der Natur.

Die Fibonacci-Zahlen weisen einige bemerkenswerte mathematische Besonderheiten auf:

• Aufgrund der Beziehung zur vorherigen und zur folgenden Zahl scheint Wachstum in der Natur einem Additionsgesetz zu folgen.
• Die Fibonacci-Folge steht in einem unmittelbaren Zusammenhang zum Goldenen Schnitt. Je weiter man in der Folge fortschreitet, desto mehr nähert sich der Quotient aufeinanderfolgender Zahlen dem Goldenen Schnitt (1,618033…) an (beispielsweise 13:8=1,6250; 21:13≈1,6154; 34:21≈1,6190; 55:34≈1,6176; etc).
• Diese Annäherung ist alternierend, d. h. die Quotienten sind abwechselnd kleiner und größer als der Goldene Schnitt.

Definition der Fibonacci-Folge

Die Fibonacci-Folge $f_{1},\,f_{2},\,f_{3},\ldots$ ist durch das rekursive Bildungsgesetz

$f_{n}=f_{n-1}+f_{n-2}$   für $n>2$

mit den Anfangswerten

$f_{1}=f_{2}=1$

definiert. Das bedeutet in Worten:

• Für die beiden ersten Zahlen wird der Wert eins vorgegeben.
• Jede weitere Zahl ist die Summe ihrer beiden Vorgänger in der Folge.

Daraus ergibt sich:

n	fn	n	fn	n	fn	n	fn	n	fn
1	1	11	89	21	10 946	31	1 346 269	41	165 580 141
2	1	12	144	22	17 711	32	2 178 309	42	267 914 296
3	2	13	233	23	28 657	33	3 524 578	43	433 494 437
4	3	14	377	24	46 368	34	5 702 887	44	701 408 733
5	5	15	610	25	75 025	35	9 227 465	45	1 134 903 170
6	8	16	987	26	121 393	36	14 930 352	46	1 836 311 903
7	13	17	1 597	27	196 418	37	24 157 817	47	2 971 215 073
8	21	18	2 584	28	317 811	38	39 088 169	48	4 807 526 976
9	34	19	4 181	29	514 229	39	63 245 986	49	7 778 742 049
10	55	20	6 765	30	832 040	40	102 334 155	50	12 586 269 025

Aus der Forderung, dass die Rekursion

$f_{n}=f_{n-1}+f_{n-2}$

auch für ganze Zahlen $n\leq 2$ gelten soll, erhält man eine eindeutige Fortsetzung auf den Index 0 und auf negative Indizes. Es gilt:

$f_{0}=0$

$f_{-n}=(-1)^{n+1}f_{n}$ für alle $n>0$

Die so erweiterte Fibonacci-Folge lautet dann

$\ldots ,\;-8,\;5,\;-3,\;2,\;-1,\;1,\;0,\;1,\;1,\;2,\;3,\;5,\;8,\;\ldots$

Darüber hinaus ist eine Verallgemeinerung der Fibonacci-Zahlen auf komplexe Zahlen, proendliche Zahlen und auf Vektorräume möglich.

Eigenschaften

Beziehungen zwischen den Folgegliedern

Identitäten:

• $f_{m+n}=f_{n+1}\;f_{m}+f_{n}\;f_{m-1}$
• $f_{m+n}=f_{n}\;L_{m}+(-1)^{m+1}\;f_{n-m}$ mit der Lucas-Folge $L_{m}=f_{m+1}+\;f_{m-1}=\Phi ^{m}+\Psi ^{m}$, insbesondere:
• $f_{2n}=f_{n}\;L_{n}=f_{n}\;(f_{n+1}+f_{n-1})$
• $f_{2n+1}=f_{n}^{2}+f_{n+1}^{2}$
• $f_{n}^{2}-f_{n+k}\;f_{n-k}=(-1)^{n-k}f_{k}^{2}$ (Identität von Catalan)
• $f_{n+1}\;f_{n-1}-f_{n}^{2}=(-1)^{n}$ (Identität von Cassini, Spezialfall der Catalan-Identität)
• $f_{m}\;f_{n+1}-f_{n}\;f_{m+1}=(-1)^{n}f_{m-n}$ (Identität von d’Ocagne)

Teilbarkeit:

• $\operatorname {ggT} (f_{m},f_{n})=f_{\operatorname {ggT} (m,n)}$
• Je zwei benachbarte Fibonaccizahlen sind teilerfremd, d. h. $\operatorname {ggT} (f_{n},f_{n+1})=1$.
• $m\mid n\Rightarrow f_{m}\mid f_{n}$; für $m>2$ gilt auch die Umkehrung. Insbesondere kann $f_{n}$ für $n>4$ nur dann eine Primzahl sein, wenn $n$ eine Primzahl ist.
• $2\mid f_{n}\Leftrightarrow 3\mid n$ (Genau jede dritte Fibonacci-Zahl ist durch 2 teilbar.)
• $3\mid f_{n}\Leftrightarrow 4\mid n$ (Genau jede vierte Fibonacci-Zahl ist durch 3 teilbar.)
• $4\mid f_{n}\Leftrightarrow 6\mid n$ (Genau jede sechste Fibonacci-Zahl ist durch 4 teilbar.)
• $5\mid f_{n}\Leftrightarrow 5\mid n$ (Genau jede fünfte Fibonacci-Zahl ist durch 5 teilbar.)
• $7\mid f_{n}\Leftrightarrow 8\mid n$ (Genau jede achte Fibonacci-Zahl ist durch 7 teilbar.)
• $16\mid f_{n}\Leftrightarrow 12\mid n$ (Genau jede zwölfte Fibonacci-Zahl ist durch 16 teilbar.)

Für die Teilbarkeit durch Primzahlen $p$ gilt unter Verwendung des Jacobi-Symbols:

• $p\mid f_{p-1}\Leftrightarrow \left({\frac {5}{p}}\right)=1$
• $p\mid f_{p+1}\Leftrightarrow \left({\frac {5}{p}}\right)=-1$

Reihen:

• $\sum _{i=0}^{n}f_{i}=f_{n+2}-1$
• $\sum _{i=1}^{2n}(-1)^{i-1}\;f_{i}=-f_{2n-1}+1$
• $\sum _{i=1}^{2n+1}(-1)^{i-1}\;f_{i}=f_{2n}+1$
• $\sum _{i=1}^{n}f_{i}^{2}=f_{n}\;f_{n+1}$
• $\sum _{i=1}^{n}f_{2i-1}=f_{2n}$
• $\sum _{i=1}^{n}f_{2i}=f_{2n+1}-1$

Es gibt noch zahlreiche weitere derartige Formeln.

Verwandtschaft mit dem Goldenen Schnitt

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

Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lim_{n \to \infty}\frac {f_{n+1}}{f_n} = \lim_{n \to \infty}{\Phi^{n+1}\over\Phi^n} = \Phi \approx 1{,}618\ldots}

Diese Quotienten zweier aufeinanderfolgender Fibonacci-Zahlen haben eine bemerkenswerte Kettenbruchdarstellung:

${\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}}}}}}}}$

Da diese Quotienten im Grenzwert gegen den goldenen Schnitt konvergieren, lässt sich dieser als der unendliche Kettenbruch

$\Phi =1+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{1+\dotsb }}}}}}}}$

darstellen.

Die Zahl $\Phi$ ist irrational. Das bedeutet, dass sie sich nicht durch ein Verhältnis zweier ganzer Zahlen darstellen lässt. Am besten lässt sich $\Phi$ durch Quotienten zweier aufeinanderfolgender Fibonacci-Zahlen approximieren. Dies gilt auch für verallgemeinerte Fibonaccifolgen, bei denen $f_{0}$ und $f_{1}$ beliebige natürliche Zahlen annehmen.

Zeckendorf-Theorem

Das nach Edouard Zeckendorf benannte Zeckendorf-Theorem besagt, dass jede natürliche Zahl $n>0$ 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=2}^{k}c_{i}f_{i}$ mit $c_{i}\in \{0,1\}$ und $c_{i}c_{i+1}=0$ für alle $i$.

Die entstehende Folge $(c)_{i}$ von Nullen und Einsen wird Zeckendorf-Sequenz genannt. Da aufeinanderfolgende Fibonacci-Zahlen ausgeschlossen sind, können keine zwei Einsen in einer Zeckendorf-Sequenz unmittelbar hintereinander stehen.

Allgemeiner ist die verwandte Aussage, dass sich jede ganze Zahl z eindeutig als Summe verschiedener, nicht direkt aufeinanderfolgender negaFibonacci-Zahlen ($f_{-k}$ mit $k\geq 1$) darstellen lässt:

$z=\sum _{i=1}^{k}c_{i}f_{-i}$ mit $c_{i}\in \{0,1\}$ und $c_{i}c_{i+1}=0$ für alle $i$.

So wäre zum Beispiel $-2=f_{-1}+f_{-4}=1-3$ als Binärsequenz 1001 darstellbar.

Zu weiteren Themen siehe auch

• Fibonacci-Folge - Artikel in der deutschen Wikipedia

Siehe auch

• Fibonacci-Folge - Artikel in der deutschen Wikipedia

Literatur

• John H. Conway, Richard K. Guy: The Book of Numbers. Copernicus NY 1996, ISBN 0-387-97993-X.
• Richard A. Dunlap: The Golden Ratio and Fibonacci Numbers. 2. Auflage. World Scientific, Singapur, 1999, ISBN 981-02-3264-0.
• Huberta Lausch: Fibonacci und die Folge(n). Oldenbourg 2010, ISBN 978-3-486-58910-8.
• Paulo Ribenboim: The New Book of Prime Number Records. Springer-Verlag 1996, ISBN 0-387-94457-5.
• The Fibonacci Quarterly. Seit 1963 vierteljährlich erscheinende Zeitschrift, die sich der Fibonacci- und verwandten Folgen widmet.

Weblinks

 Wikibooks: Algorithmensammlung: Zahlentheorie: Fibonacci-Folge – Lern- und Lehrmaterialien

Commons: Fibonacci numbers - Weitere Bilder oder Audiodateien zum Thema

• Fibonacci-Zahlen – sehr ausführliche Seite mit weiterführenden Themen
• Fibonacci Numbers and the Golden Section (englisch)
• Fibonacci und der Goldene Schnitt (PDF; 1,22 MB)
• Video: Die Fibonacci-Zahlen (aus der Fernsehsendung Mathematik zum Anfassen des Senders BR-alpha) von Albrecht Beutelspacher
• Fibonacci Numbers and the Pascal Triangle (englisch, deutsch, serbisch)
• Die Fibonacci-Zahlen und ihre Bedeutung in der Natur YouTube