imported>Joachim Stiller |
imported>Odyssee |
Zeile 1: |
Zeile 1: |
| [[Datei:FibonacciBlocks.svg|mini|Kachelmuster aus Quadraten, deren Kantenlängen der Fibonacci-Folge entsprechen]]
| | #WEITERLEITUNG [[Zellmembran]] |
| Die '''Fibonacci-Folge''' ist die unendliche [[Folge (Mathematik)|Folge]] von [[Natürliche Zahl|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.<ref name=OESI2C>{{OEIS|A000045}}</ref> Im Anschluss ergibt jeweils die Summe zweier aufeinanderfolgender Zahlen die unmittelbar danach folgende Zahl:
| |
| {|
| |
| | [[Datei:Fibonacci sequence - optional starting with zero.jpg|links|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 [[Antikes Griechenland|Griechen]] als auch den [[Indien|Indern]] bekannt.<ref>{{Cite journal |first=Parmanand |last=Singh |title=The So-called Fibonacci numbers in ancient and medieval India |journal=Historia Mathematica |volume=12 |issue=3 |pages=229–244 |year=1985 |doi=10.1016/0315-0860(85)90021-7}}</ref>
| |
| | |
| Weitere Untersuchungen zeigten, dass die Fibonacci-Folge auch noch zahlreiche andere [[#Fibonacci-Folgen in der Natur|Wachstumsvorgänge der Pflanzen]] beschreibt. Es scheint, als sei sie eine Art Wachstumsmuster in der Natur.<ref name=GoSecEu>Ruben Stelzner (in Zusammenarbeit mit Wolfgang Schad): ''[http://www.golden-section.eu/kapitel5.html Der Goldene Schnitt. Das Mysterium der Schönheit.]'' In: ''golden-section.eu.'' Abgerufen am 26. Oktober 2015.</ref>
| |
| | |
| Die Fibonacci-Zahlen weisen einige bemerkenswerte mathematische Besonderheiten auf:
| |
| * Aufgrund der [[#Beziehungen zwischen den Folgegliedern|Beziehung zur vorherigen und zur folgenden Zahl]] scheint Wachstum in der Natur einem Additionsgesetz zu folgen.
| |
| * Die Fibonacci-Folge steht in einem unmittelbaren [[#Verwandtschaft mit dem Goldenen Schnitt|Zusammenhang zum Goldenen Schnitt]]. Je weiter man in der Folge fortschreitet, desto mehr nähert sich der [[Quotient]] aufeinanderfolgender Zahlen dem [[Goldener Schnitt|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.<ref name=GoSecEu />
| |
| | |
| == Definition der Fibonacci-Folge ==
| |
| | |
| Die Fibonacci-Folge <math>f_1,\,f_2,\,f_3,\ldots</math> ist durch das [[Rekursion|rekursive]] Bildungsgesetz
| |
| | |
| : <math>f_n = f_{n-1} + f_{n-2}</math> für <math>n > 2</math>
| |
| | |
| mit den Anfangswerten
| |
| | |
| : <math>f_1 = f_2 = 1</math>
| |
| | |
| 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:
| |
| | |
| :{| class="wikitable" style="text-align:right"
| |
| ! n
| |
| ! ''f''<sub>n</sub>
| |
| ! style="border-left:medium solid" |n
| |
| ! ''f''<sub>n</sub>
| |
| ! style="border-left:medium solid" |n
| |
| ! ''f''<sub>n</sub>
| |
| ! style="border-left:medium solid" |n
| |
| ! ''f''<sub>n</sub>
| |
| ! style="border-left:medium solid" |n
| |
| ! ''f''<sub>n</sub>
| |
| |-
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 1 || style="border-right:medium solid" | 1
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 11 || style="border-right:medium solid" | 89
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 21 || style="border-right:medium solid" | 10 946
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 31 || style="border-right:medium solid" | 1 346 269
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 41 || 165 580 141
| |
| |-
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 2 || style="border-right:medium solid" | 1
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 12 || style="border-right:medium solid" | 144
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 22 || style="border-right:medium solid" | 17 711
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 32 || style="border-right:medium solid" | 2 178 309
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 42 || 267 914 296
| |
| |-
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 3 || style="border-right:medium solid" | 2
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 13 || style="border-right:medium solid" | 233
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 23 || style="border-right:medium solid" | 28 657
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 33 || style="border-right:medium solid" | 3 524 578
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 43 || 433 494 437
| |
| |-
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 4 || style="border-right:medium solid" | 3
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 14 || style="border-right:medium solid" | 377
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 24 || style="border-right:medium solid" | 46 368
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 34 || style="border-right:medium solid" | 5 702 887
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 44 || 701 408 733
| |
| |-
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 5 || style="border-right:medium solid" | 5
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 15 || style="border-right:medium solid" | 610
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 25 || style="border-right:medium solid" | 75 025
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 35 || style="border-right:medium solid" | 9 227 465
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 45 || 1 134 903 170
| |
| |-
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 6 || style="border-right:medium solid" | 8
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 16 || style="border-right:medium solid" | 987
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 26 || style="border-right:medium solid" | 121 393
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 36 || style="border-right:medium solid" | 14 930 352
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 46 || 1 836 311 903
| |
| |-
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 7 || style="border-right:medium solid" | 13
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 17 || style="border-right:medium solid" | 1 597
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 27 || style="border-right:medium solid" | 196 418
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 37 || style="border-right:medium solid" | 24 157 817
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 47 || 2 971 215 073
| |
| |-
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 8 || style="border-right:medium solid" | 21
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 18 || style="border-right:medium solid" | 2 584
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 28 || style="border-right:medium solid" | 317 811
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 38 || style="border-right:medium solid" | 39 088 169
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 48 || 4 807 526 976
| |
| |-
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 9 || style="border-right:medium solid" | 34
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 19 || style="border-right:medium solid" | 4 181
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 29 || style="border-right:medium solid" | 514 229
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 39 || style="border-right:medium solid" | 63 245 986
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 49 || 7 778 742 049
| |
| |-
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 10 || style="border-right:medium solid" | 55
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 20 || style="border-right:medium solid" | 6 765
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 30 || style="border-right:medium solid" | 832 040
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 40 || style="border-right:medium solid" | 102 334 155
| |
| | style="padding:0ex 2ex 0ex 1ex;"| 50 || 12 586 269 025
| |
| |-
| |
| |}
| |
| | |
| Aus der Forderung, dass die Rekursion
| |
| | |
| : <math>f_n = f_{n-1} + f_{n-2}</math>
| |
| | |
| auch für ganze Zahlen <math>n \leq 2</math> gelten soll, erhält man eine eindeutige Fortsetzung auf den Index 0 und auf negative Indizes. Es gilt:
| |
| | |
| : <math>f_0 = 0</math>
| |
| : <math>f_{-n} = (-1)^{n+1} f_n</math> für alle <math>n > 0</math>
| |
| | |
| Die so erweiterte Fibonacci-Folge lautet dann
| |
| | |
| : <math>\ldots,\;-8,\;5,\;-3,\;2,\;-1,\;1,\;0,\;1,\;1,\;2,\;3,\;5,\;8,\;\ldots</math>
| |
| | |
| Darüber hinaus ist eine [[Verallgemeinerte Fibonacci-Folge|Verallgemeinerung der Fibonacci-Zahlen]] auf [[komplexe Zahl]]en, [[proendliche Zahl]]en<ref>Hendrik Lenstra: [http://www.math.leidenuniv.nl/~hwl/papers/fibo.pdf ''Profinite Fibonacci numbers''.] (PDF)</ref> und auf [[Vektorraum|Vektorräume]] möglich.
| |
| | |
| == Eigenschaften ==
| |
| | |
| === Beziehungen zwischen den Folgegliedern ===
| |
| [[Identitätsgleichung|Identitäten]]:
| |
| * <math>f_{m+n} = f_{n+1} \; f_m + f_n \; f_{m-1}</math>
| |
| * <math>f_{m+n} = f_n\; L_m + (-1)^{m+1} \; f_{n-m}</math> mit der [[Lucas-Folge]] <math>L_m=f_{m+1}+\;f_{m-1}=\Phi^m+\Psi^m</math>, insbesondere:
| |
| * <math>f_{2n} = f_n\; L_n = f_n\; (f_{n+1}+f_{n-1})</math>
| |
| * <math>f_{2n+1} = f_n^2 + f_{n+1}^2</math>
| |
| * <math>f_{n}^2 - f_{n+k} \; f_{n-k}=(-1)^{n-k} f_{k}^2</math> (Identität von [[Eugène Charles Catalan|Catalan]])
| |
| * <math>f_{n+1} \; f_{n-1} - f_{n}^2=(-1)^{n} </math> (Identität von [[Giovanni Domenico Cassini|Cassini]], Spezialfall der Catalan-Identität)
| |
| * <math>f_{m} \; f_{n+1} - f_{n} \; f_{m+1}=(-1)^{n} f_{m-n} </math> (Identität von [[Philbert Maurice d’Ocagne|d’Ocagne]])
| |
| | |
| [[Teilbarkeit]]:
| |
| * <math>\operatorname{ggT}(f_m,f_n)=f_{\operatorname{ggT}(m,n)}</math>
| |
| * Je zwei benachbarte Fibonaccizahlen sind teilerfremd, d. h. <math>\operatorname{ggT}(f_n,f_{n+1})=1</math>.
| |
| * <math>m\mid n\Rightarrow f_m\mid f_n</math>; für <math>m>2</math> gilt auch die Umkehrung. Insbesondere kann <math>f_n</math> für <math>n>4</math> nur dann eine [[Primzahl]] sein, wenn <math>n</math> eine Primzahl ist.
| |
| * <math>2 \mid f_n \Leftrightarrow 3 \mid n</math> (Genau jede dritte Fibonacci-Zahl ist durch 2 teilbar.)
| |
| * <math>3 \mid f_n \Leftrightarrow 4 \mid n</math> (Genau jede vierte Fibonacci-Zahl ist durch 3 teilbar.)
| |
| * <math>4 \mid f_n \Leftrightarrow 6 \mid n</math> (Genau jede sechste Fibonacci-Zahl ist durch 4 teilbar.)
| |
| * <math>5 \mid f_n \Leftrightarrow 5 \mid n</math> (Genau jede fünfte Fibonacci-Zahl ist durch 5 teilbar.)
| |
| * <math>7 \mid f_n \Leftrightarrow 8 \mid n</math> (Genau jede achte Fibonacci-Zahl ist durch 7 teilbar.)
| |
| * <math>16 \mid f_n \Leftrightarrow 12 \mid n</math> (Genau jede zwölfte Fibonacci-Zahl ist durch 16 teilbar.)<ref>Nicolai N. Vorobiev: ''Fibonacci Numbers.'' Birkhäuser, Basel 2002. ISBN 3-7643-6135-2. S. 59, [http://books.google.de/books?id=uVE_LiXbSpoC&pg=PA59#v=onepage&q&f=false Online-Version].</ref>
| |
| :Für die Teilbarkeit durch Primzahlen <math>p</math> gilt unter Verwendung des [[Quadratischer Rest#Legendre- und Jacobi-Symbol|Jacobi-Symbols]]:
| |
| * <math>p \mid f_{p-1} \Leftrightarrow \left(\frac{5}{p}\right)=1</math>
| |
| * <math>p \mid f_{p+1} \Leftrightarrow \left(\frac{5}{p}\right)=-1</math><ref>[http://sternenreise.com/Verschiedenes/Fibonacci-Teilbarkeit.pdf PDF.] Bei: ''sternenreise.com.''</ref>
| |
| | |
| [[Reihe (Mathematik)|Reihen]]:
| |
| * <math>\sum_{i=0}^{n} f_i = f_{n+2}-1</math>
| |
| * <math>\sum_{i=1}^{2n} (-1)^{i-1} \; f_i = -f_{2n-1}+1</math>
| |
| * <math>\sum_{i=1}^{2n+1} (-1)^{i-1} \; f_i = f_{2n}+1</math>
| |
| * <math>\sum_{i=1}^{n} f_i^2 = f_n \; f_{n+1}</math>
| |
| * <math>\sum_{i=1}^{n} f_{2i-1} = f_{2n}</math>
| |
| * <math>\sum_{i=1}^{n} f_{2i} = f_{2n+1}-1</math>
| |
| | |
| 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 [[Goldener Schnitt|Goldenen Schnitt]] <math>\Phi</math> an. Dies folgt unmittelbar aus der [[Fibonacci-Folge#Näherungsformel für große Zahlen|Näherungsformel]] für große <math>n:</math>
| |
| | |
| :<math>\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</math>
| |
| | |
| Diese Quotienten zweier aufeinanderfolgender Fibonacci-Zahlen haben eine bemerkenswerte [[Kettenbruch]]darstellung:
| |
| :<math>\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}}}}</math>
| |
| | |
| Da diese Quotienten im Grenzwert gegen den goldenen Schnitt konvergieren, lässt sich dieser als der unendliche Kettenbruch
| |
| :<math>\Phi = 1+\cfrac{1}{1+ \cfrac{1}{1+ \cfrac{1}{1+ \cfrac{1}{1+\dotsb}}}}</math>
| |
| darstellen.
| |
| | |
| Die Zahl <math>\Phi</math> ist [[irrationale Zahl|irrational]]. Das bedeutet, dass sie sich nicht durch ein Verhältnis zweier ganzer Zahlen darstellen lässt. Am besten lässt sich <math>\Phi</math> durch Quotienten zweier aufeinanderfolgender Fibonacci-Zahlen approximieren. Dies gilt auch für verallgemeinerte Fibonaccifolgen, bei denen <math>f_0</math> und <math>f_1</math> beliebige natürliche Zahlen annehmen.
| |
| | |
| === Zeckendorf-Theorem ===
| |
| Das nach [[Edouard Zeckendorf]] benannte Zeckendorf-Theorem besagt, dass jede natürliche Zahl <math>n > 0</math> eindeutig als Summe voneinander verschiedener, nicht direkt aufeinanderfolgender Fibonacci-Zahlen geschrieben werden kann. Das heißt, es gibt für jedes <math>n \in \mathbb{N}, n > 0</math> eine eindeutige Darstellung der Form
| |
| | |
| :<math>n = \sum_{i=2}^{k} c_i f_i</math> mit <math>c_i\in \{0, 1\}</math> und <math>c_ic_{i+1}=0</math> für alle <math>i</math>.
| |
| | |
| Die entstehende Folge <math>(c)_i</math> 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 (<math>f_{-k}</math> mit <math>k\geq 1</math>) darstellen lässt:
| |
| :<math>z = \sum_{i=1}^{k} c_i f_{-i}</math> mit <math>c_i\in \{0, 1\}</math> und <math>c_ic_{i+1}=0</math> für alle <math>i</math>.
| |
| So wäre zum Beispiel <math>-2 = f_{-1} + f_{-4} = 1-3</math> als Binärsequenz <code>1001</code> darstellbar.<ref>{{Literatur |Autor=Donald E. Knuth |Titel=The Art Of Computer Programming Vol. IV}}</ref>
| |
| | |
| == Zu weiteren Themen siehe auch ==
| |
| * {{WikipediaDE|Fibonacci-Folge}}
| |
| | |
| == Siehe auch ==
| |
| * {{WikipediaDE|Fibonacci-Folge}}
| |
| | |
| == 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.
| |
| * [http://www.fq.math.ca/list-of-issues.html ''The Fibonacci Quarterly.''] Seit 1963 vierteljährlich erscheinende Zeitschrift, die sich der Fibonacci- und verwandten Folgen widmet.
| |
| | |
| == Weblinks ==
| |
| {{Wikibooks|Algorithmensammlung: Zahlentheorie: Fibonacci-Folge}}
| |
| {{Commonscat|Fibonacci numbers}}
| |
| * [http://www.ijon.de/mathe/fibonacci/index.html Fibonacci-Zahlen] – sehr ausführliche Seite mit weiterführenden Themen
| |
| * [http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fib.html Fibonacci Numbers and the Golden Section] (englisch)
| |
| * [http://chorgiessen.altervista.org/jab/goldfibo/goldfibo.pdf Fibonacci und der Goldene Schnitt] (PDF; 1,22 MB)
| |
| * Video: [https://www.br.de/fernsehen/ard-alpha/sendungen/mathematik-zum-anfassen/mathematik-zum-anfassen-fibonacci-zahlen100.html Die Fibonacci-Zahlen] (aus der Fernsehsendung ''Mathematik zum Anfassen'' des Senders BR-alpha) von Albrecht Beutelspacher
| |
| * [http://milan.milanovic.org/math/ Fibonacci Numbers and the Pascal Triangle] (englisch, deutsch, serbisch)
| |
| | |
| == Einzelnachweise ==
| |
| <references />
| |
| | |
| {{SORTIERUNG:Fibonaccifolge}}
| |
| [[Kategorie:Folgen und Reihen]]
| |
| [[Kategorie:Zahlentheorie]]
| |
| [[Kategorie:Biologie]] | |
| | |
| {{Wikipedia}}
| |