Fibonacci-Zahl - Fibonacci number

Eine Kachelung mit Quadraten, deren Seitenlängen aufeinanderfolgende Fibonacci-Zahlen sind: 1, 1, 2, 3, 5, 8, 13 und 21.

In der Mathematik bilden die Fibonacci-Zahlen , allgemein als F n bezeichnet , eine Folge , die als Fibonacci-Folge bezeichnet wird , so dass jede Zahl die Summe der beiden vorhergehenden ist, beginnend bei 0 und 1. Das heißt,

und
für n > 1 .

Die Sequenz beginnt:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

Bei einigen älteren Definitionen wird der Wert weggelassen, damit die Sequenz mit beginnt und die Wiederholung für n > 2 gültig ist . In seiner ursprünglichen Definition begann Fibonacci die Folge mit

Die Fibonacci-Spirale: eine Annäherung an die goldene Spirale, die durch das Zeichnen von Kreisbögen entsteht, die die gegenüberliegenden Ecken der Quadrate in der Fibonacci-Kachelung verbinden; (siehe vorheriges Bild)

Fibonacci-Zahlen sind stark mit dem Goldenen Schnitt verbunden : Binets Formel drückt die n- te Fibonacci-Zahl in Bezug auf n und den Goldenen Schnitt aus und impliziert, dass das Verhältnis zweier aufeinanderfolgender Fibonacci-Zahlen mit zunehmendem n zum Goldenen Schnitt tendiert .

Fibonacci-Zahlen sind nach dem italienischen Mathematiker Leonardo von Pisa, später bekannt als Fibonacci, benannt . In seinem 1202 Buch Liber Abaci eingeführt, Fibonacci um die Sequenz zu westeuropäischer Mathematik, obwohl die Sequenz in früher beschrieben worden war indische Mathematik , so früh wie 200 vor Christus in der Arbeit von Pingala auf Aufzählen mögliche Muster von Sanskrit Poesie aus Silben von zwei Längen gebildet.

Fibonacci-Zahlen tauchen unerwartet oft in der Mathematik auf, so dass ihr eine ganze Zeitschrift gewidmet ist, das Fibonacci Quarterly . Zu den Anwendungen von Fibonacci-Zahlen gehören Computeralgorithmen wie die Fibonacci-Suchtechnik und die Fibonacci-Heap- Datenstruktur sowie Graphen, die Fibonacci-Würfel genannt werden, die zum Verbinden paralleler und verteilter Systeme verwendet werden.

Sie treten auch in biologischen Umgebungen auf , wie zum Beispiel bei der Verzweigung von Bäumen, der Anordnung von Blättern an einem Stiel , den Fruchtsprossen einer Ananas , der Blüte einer Artischocke , einem sich entfaltenden Farn und der Anordnung der Hochblätter eines Tannenzapfens .

Fibonacci-Zahlen sind auch insofern eng mit Lucas-Zahlen verwandt , als die Fibonacci- und Lucas-Zahlen ein komplementäres Paar von Lucas-Folgen bilden : und .

Geschichte

Dreizehn ( F 7 ) Möglichkeiten, lange (durch rote Kacheln dargestellt) und kurze Silben (durch graue Quadrate dargestellt) in einer Kadenz der Länge sechs anzuordnen. Fünf ( F 5 ) enden mit einer langen Silbe und acht ( F 6 ) enden mit einer kurzen Silbe.

Die Fibonacci-Folge erscheint in der indischen Mathematik in Verbindung mit der Sanskrit-Prosodie , wie Parmanand Singh 1986 betonte. S) Silben von 1 Einheit Dauer. Das Zählen der verschiedenen Muster aufeinanderfolgender L und S mit einer gegebenen Gesamtdauer ergibt die Fibonacci-Zahlen: Die Anzahl der Muster der Dauer m Einheiten ist F m + 1 .

Die Kenntnis der Fibonacci-Folge wurde bereits in Pingala ( ca.  450 v . Chr.–200 v. Chr.) zum Ausdruck gebracht . Singh zitiert Pingalas kryptische Formel misrau cha ("die beiden sind gemischt") und Gelehrte, die sie im Kontext so interpretieren, dass sie sagen, dass die Anzahl der Muster für m Beats ( F m +1 ) erhalten wird, indem man ein [S] zu F m . addiert Fällen und ein [L] zu den F m −1 Fällen. Bharata Muni drückt auch die Kenntnis der Sequenz in der Natya Shastra (ca. 100 v. Chr. – ca. 350 n. Chr.) aus. Die deutlichste Darstellung der Sequenz ergibt sich jedoch im Werk von Virahanka (um 700 n. Chr.), dessen eigenes Werk verloren geht, aber in einem Zitat von Gopala (um 1135) verfügbar ist:

Variationen von zwei früheren Metern [ist die Variation]... Zum Beispiel, für [einen Meter Länge] vier, Variationen von zwei Metern [und] drei, werden gemischt, fünf passieren. [arbeitet Beispiele 8, 13, 21]... Auf diese Weise sollte der Prozess in allen mātrā-vṛttas [prosodischen Kombinationen] befolgt werden .

Hemachandra (ca. 1150) wird auch die Kenntnis der Sequenz zugeschrieben, die schreibt, dass "die Summe der letzten und der vorletzten die Zahl ... der nächsten mātrā-vṛtta ist."

Eine Seite des Fibonacci ‚s Liber Abaci aus der Biblioteca Nazionale di Firenze (im Kasten auf der rechten Seite ), die die Fibonacci - Sequenz mit der Position in der in lateinischen und römischen Ziffern und dem Wert in Hindu-arabische Ziffern beschriftet Sequenz.
Die Anzahl der Kaninchenpaare bildet die Fibonacci-Folge

Außerhalb Indiens erscheint die Fibonacci-Folge erstmals im Buch Liber Abaci ( The Book of Calculation , 1202) von Fibonacci, wo sie zur Berechnung des Wachstums von Kaninchenpopulationen verwendet wird. Fibonacci betrachtet das Wachstum einer idealisierten (biologisch unrealistischen) Kaninchenpopulation unter der Annahme, dass: ein neugeborenes Zuchtpaar von Kaninchen auf ein Feld gebracht wird; jedes Brutpaar paart sich im Alter von einem Monat, und am Ende des zweiten Monats bringen sie immer ein weiteres Kaninchenpaar zur Welt; und Kaninchen sterben nie, sondern züchten für immer weiter. Fibonacci stellte das Rätsel: Wie viele Paare wird es in einem Jahr geben?

  • Am Ende des ersten Monats paaren sie sich, aber es gibt immer noch nur 1 Paar.
  • Am Ende des zweiten Monats produzieren sie ein neues Paar, es sind also 2 Paare im Feld.
  • Am Ende des dritten Monats bringt das ursprüngliche Paar ein zweites Paar hervor, aber das zweite Paar paart sich nur ohne Brut, so dass es insgesamt 3 Paare gibt.
  • Am Ende des vierten Monats hat das ursprüngliche Paar ein weiteres neues Paar hervorgebracht, und das vor zwei Monaten geborene Paar produziert auch sein erstes Paar, also 5 Paare.

Am Ende des n- ten Monats entspricht die Anzahl der Kaninchenpaare der Anzahl der ausgewachsenen Paare (dh der Anzahl der Paare im Monat n – 2 ) plus der Anzahl der im letzten Monat lebenden Paare (Monat n – 1 .). ). Die Zahl im n- ten Monat ist die n- te Fibonacci-Zahl.

Der Name "Fibonacci-Folge" wurde erstmals von dem Zahlentheoretiker Édouard Lucas des 19. Jahrhunderts verwendet .

Sequenzeigenschaften

Die ersten 21 Fibonacci-Zahlen F n sind:

F 0 F 1 F 2 F 3 F 4 F 5 F 6 F 7 F 8 F 9 F 10 F 11 F 12 F 13 F 14 F 15 F 16 F 17 F 18 F 19 F 20
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

Die Folge kann auch auf den negativen Index n erweitert werden, indem die umgeordnete Wiederholungsbeziehung verwendet wird

was die Folge von "Negafibonacci"-Zahlen ergibt, die

Die bidirektionale Folge ist also

F -8 F -7 F -6 F -5 F -4 F -3 F -2 F -1 F 0 F 1 F 2 F 3 F 4 F 5 F 6 F 7 F 8
−21 13 -8 5 -3 2 -1 1 0 1 1 2 3 5 8 13 21

Beziehung zum Goldenen Schnitt

Geschlossener Ausdruck

Wie jede Folge, die durch eine lineare Rekursion mit konstanten Koeffizienten definiert ist , haben die Fibonacci-Zahlen einen geschlossenen Ausdruck . Sie wurde als Binets Formel bekannt , benannt nach dem französischen Mathematiker Jacques Philippe Marie Binet , obwohl sie bereits von Abraham de Moivre und Daniel Bernoulli bekannt war :

wo
ist der Goldene Schnitt ( OEISA001622 ) und

Da kann diese Formel auch geschrieben werden als

Um dies zu sehen, beachte, dass φ und ψ beide Lösungen der Gleichungen sind
also erfüllen die Potenzen von φ und ψ die Fibonacci-Rekursion. Mit anderen Worten,
und

Daraus folgt, dass für alle Werte a und b die durch . definierte Folge

erfüllt die gleiche Wiederholung.

Wenn a und b so gewählt werden, dass U 0 = 0 und U 1 = 1 ist, dann muss die resultierende Folge U n die Fibonacci-Folge sein. Dies ist dasselbe, als ob a und b das Gleichungssystem erfüllen müssen:

was hat lösung
die erforderliche Formel herstellen.

Nimmt man die Startwerte U 0 und U 1 als willkürliche Konstanten, so lautet eine allgemeinere Lösung:

wo

Berechnung durch Rundung

Schon seit

für alle n ≥ 0 ist die Zahl F n die nächste ganze Zahl zu . Daher kann es durch

Runden mit der nächsten ganzzahligen Funktion gefunden werden:

Tatsächlich ist der Rundungsfehler sehr klein und beträgt weniger als 0,1 für n 4 und weniger als 0,01 für n 8 .

Fibonacci-Zahlen können auch durch Kürzung berechnet werden , in Bezug auf die Bodenfunktion :

Da die Floor-Funktion monoton ist , kann letztere Formel invertiert werden, um den Index n ( F ) der größten Fibonacci-Zahl zu finden, die nicht größer als eine reelle Zahl F > 1 ist :

wo

Grenze aufeinanderfolgender Quotienten

Johannes Kepler beobachtete, dass das Verhältnis aufeinanderfolgender Fibonacci-Zahlen konvergiert. Er schrieb, dass "wie 5 zu 8 ist, so ist auch 8 zu 13, und wie 8 zu 13 ist, so ist 13 zu 21 fast", und kam zu dem Schluss, dass diese Verhältnisse sich dem Goldenen Schnitt nähern

Diese Konvergenz gilt unabhängig von den Startwerten, mit Ausnahme von 0 und 0, oder einem beliebigen Paar im konjugierten Goldenen Schnitt. Dies kann mit der

Binet-Formel überprüft werden . Zum Beispiel erzeugen die Anfangswerte 3 und 2 die Folge 3, 2, 5, 7, 12, 19, 31, 50, 81, 131, 212, 343, 555, ... Das Verhältnis der aufeinanderfolgenden Terme in dieser Folge zeigt die gleiche Konvergenz zum Goldenen Schnitt.
Aufeinanderfolgende Kacheln der Ebene und ein Graph mit Annäherungen an den Goldenen Schnitt, berechnet durch Dividieren jeder Fibonacci-Zahl durch die vorherige

Zerlegung von Kräften

Da der Goldene Schnitt die Gleichung erfüllt

dieser Ausdruck kann verwendet werden, um höhere Potenzen als lineare Funktion niedrigerer Potenzen zu zerlegen, die wiederum bis hinunter in eine Linearkombination von und 1 zerlegt werden können . Die resultierenden

Rekursionsbeziehungen liefern Fibonacci-Zahlen als lineare Koeffizienten:
Diese Gleichung kann durch Induktion nach n bewiesen werden .

Dieser Ausdruck gilt auch für n <1 , wenn die Fibonacci - Folge F n wird auf negative ganze Zahlen erweitert mit der Fibonacci - Regel

Matrixform

Ein 2-dimensionales System linearer Differenzengleichungen , das die Fibonacci-Folge beschreibt, ist

alternativ bezeichnet

was ergibt . Die

Eigenwerte der Matrix A sind und entsprechen den jeweiligen Eigenvektoren
und
Da der Anfangswert ist
daraus folgt, dass der n- te Term
Daraus lässt sich das n- te Element der Fibonacci-Reihe direkt als geschlossener Ausdruck ablesen :

Äquivalent kann die gleiche Berechnung durch Diagonalisierung von A unter Verwendung seiner Eigenzerlegung durchgeführt werden :

wobei und Der geschlossene Ausdruck für das n- te Element in der Fibonacci-Reihe ist daher gegeben durch

was wiederum ergibt

Die Matrix A hat eine Determinante von −1 und ist somit eine 2×2 unimodulare Matrix .

Diese Eigenschaft kann in Bezug auf die Kettenbruchdarstellung für den Goldenen Schnitt verstanden werden:

Die Fibonacci-Zahlen treten als Verhältnis aufeinanderfolgender Konvergenten des Kettenbruchs für φ auf , und die aus aufeinanderfolgenden Konvergenten eines Kettenbruchs gebildete Matrix hat eine Determinante von +1 oder -1. Die Matrixdarstellung liefert den folgenden geschlossenen Ausdruck für die Fibonacci-Zahlen:

Nimmt man die Determinante beider Seiten dieser Gleichung, erhält man Cassinis Identität ,

Da darüber hinaus

A n A m = A n + m für jede quadratische Matrix A können die folgenden Identitäten abgeleitet werden (sie werden von zwei verschiedenen Koeffizienten des Matrixproduktes erhalten wird , und man kann bequem die zweiten von dem ersten ableiten von n in n + 1 ändern ),

Insbesondere mit m = n ,

Diese letzten beiden Identitäten bieten eine Möglichkeit, Fibonacci-Zahlen rekursiv in O (log( n )) arithmetischen Operationen und in der Zeit O ( M ( n ) log ( n ) ) zu berechnen , wobei M ( n ) die Zeit für die Multiplikation von zwei ist Zahlen mit n Stellen. Dies entspricht der Zeit für die Berechnung der n- ten Fibonacci-Zahl aus der geschlossenen Matrixformel, jedoch mit weniger redundanten Schritten, wenn man die Neuberechnung einer bereits berechneten Fibonacci-Zahl (Rekursion mit Memoisierung ) vermeidet .

Identifikation

Es stellt sich die Frage, ob eine positive ganze Zahl x eine Fibonacci-Zahl ist. Dies ist genau dann wahr, wenn mindestens eines von oder ein

perfektes Quadrat ist . Dies liegt daran, dass die obige Formel von Binet so umgeordnet werden kann, dass

die es einem ermöglicht, die Position in der Folge einer gegebenen Fibonacci-Zahl zu finden.

Diese Formel muss eine ganze Zahl für alle n zurückgeben , daher muss der radikale Ausdruck eine ganze Zahl sein (sonst gibt der Logarithmus nicht einmal eine rationale Zahl zurück).

Kombinatorische Identitäten

Kombinatorische Beweise

Die meisten Identitäten, die Fibonacci-Zahlen beinhalten, können mit kombinatorischen Argumenten unter Verwendung der Tatsache bewiesen werden , die als Anzahl von [möglicherweise leeren] Folgen von Einsen und Zweien interpretiert werden kann, deren Summe ist . Dies kann als Definition von mit den Konventionen genommen werden , was bedeutet, dass es keine solche Folge gibt, deren Summe −1 ist, und , was bedeutet, dass die leere Folge zu 0 "aufaddiert" wird. Im Folgenden ist die

Kardinalität einer Menge:

Auf diese Weise ist die Rekursionsrelation

kann verstanden werden, indem man die Sequenzen in zwei sich nicht überlappende Mengen teilt, wobei alle Sequenzen entweder mit 1 oder 2 beginnen:
Ohne das erste Element summieren sich die verbleibenden Terme in jeder Folge zu oder und die
Kardinalität jeder Menge ist oder, was eine Gesamtzahl von Folgen ergibt, was zeigt, dass dies gleich ist .


In ähnlicher Weise kann gezeigt werden, dass die Summe der ersten Fibonacci-Zahlen bis zum n- ten gleich der ( n + 2)-ten Fibonacci-Zahl minus 1 ist. In Symbolen:

Dies kann gesehen werden, indem alle Sequenzen, die sich zu summieren, basierend auf der Position der ersten 2 geteilt werden. Insbesondere besteht jeder Satz aus den Sequenzen, die bis zu den letzten beiden Sätzen jeweils mit Kardinalität 1 beginnen.


Der gleichen Logik wie zuvor folgend, sehen wir durch Summieren der Kardinalität jeder Menge, dass

... wobei die letzten beiden Terme den Wert haben . Daraus folgt das .

Ein ähnliches Argument, das die Summen nach der Position der ersten 1 statt der ersten 2 gruppiert, ergibt zwei weitere Identitäten:

und
In Worten, die Summe der ersten Fibonacci-Zahlen mit ungeradem Index bis ist die (2
n )-te Fibonacci-Zahl, und die Summe der ersten Fibonacci-Zahlen mit geradem Index bis ist die (2 n  + 1)-te Fibonacci-Zahl minus 1.


Ein anderer Trick kann verwendet werden, um zu beweisen

oder in Worten, die Summe der Quadrate der ersten Fibonacci-Zahlen bis zu dem Produkt der
n- ten und ( n  + 1)-ten Fibonacci-Zahlen. Um dies zu sehen, beginnen Sie mit einem Fibonacci-Rechteck der Größe und zerlegen Sie es in Quadrate der Größe ; daraus folgt die Identität durch Flächenvergleich:
34*21-FibonacciBlocks.png

Symbolische Methode

Die Reihenfolge wird auch mit der

symbolischen Methode betrachtet . Genauer gesagt entspricht diese Folge einer angebbaren kombinatorischen Klasse . Die Spezifikation dieser Sequenz ist . Tatsächlich entspricht die -te Fibonacci-Zahl , wie oben erwähnt, der Anzahl der kombinatorischen Kompositionen (geordnete Partitionen ) unter Verwendung der Terme 1 und 2.

Daraus folgt, dass die gewöhnliche erzeugende Funktion der Fibonacci-Folge, dh die komplexe Funktion ist .

Induktionsnachweise

Fibonacci-Identitäten können oft leicht durch mathematische Induktion bewiesen werden .

Überdenken Sie zum Beispiel

Hinzufügen zu beiden Seiten ergibt

und damit haben wir die Formel für

Fügen Sie auf ähnliche Weise zu beiden Seiten von hinzu

geben

Binet Formel Beweise

Die Binet-Formel lautet

Dies kann verwendet werden, um Fibonacci-Identitäten zu beweisen.

Um zum Beispiel zu beweisen, dass die linke Seite multipliziert mit . wird

nach Bedarf, unter Verwendung der Fakten und zur Vereinfachung der Gleichungen.

Andere Identitäten

Zahlreiche andere Identitäten können mit verschiedenen Methoden abgeleitet werden. Hier sind einige davon:

Cassinis und Katalanens Identitäten

Cassinis Identität besagt, dass

Die katalanische Identität ist eine Verallgemeinerung:

d'Ocagnes Identität

wobei L n die n- te Lucas-Zahl ist . Der letzte ist eine Identität zum Verdoppeln von n ; andere Identitäten dieser Art sind
von Cassinis Identität.

Diese können experimentell unter Verwendung der Gitterreduktion gefunden werden und sind nützlich beim Einrichten des speziellen Zahlenfeldsiebs, um eine Fibonacci-Zahl zu faktorisieren .

Allgemeiner,

oder alternativ

Setzt man k = 2 in diese Formel, erhält man wieder die Formeln vom Ende des obigen Abschnitts Matrixform .

Generierungsfunktion

Die erzeugende Funktion der Fibonacci-Folge ist die Potenzreihe

Diese Reihe ist konvergent für und ihre Summe hat eine einfache geschlossene Form:

Dies kann bewiesen werden, indem man die Fibonacci-Rekursion verwendet, um jeden Koeffizienten in der unendlichen Summe zu erweitern:

Lösen der Gleichung

für s ( x ) ergibt sich die geschlossene Form.

gibt die erzeugende Funktion für die Negafibonacci- Zahlen und erfüllt die

Funktionalgleichung

Die Partialbruchzerlegung ist gegeben durch

wo ist der goldene Schnitt und ist seine Konjugation.

Gegenseitige Summen

Unendliche Summen über reziproke Fibonacci-Zahlen können manchmal in Form von Theta-Funktionen ausgewertet werden . Zum Beispiel können wir die Summe jeder ungeraden indizierten reziproken Fibonacci-Zahl schreiben als

und die Summe der quadrierten reziproken Fibonacci-Zahlen als

Wenn wir in der ersten Summe zu jeder Fibonacci-Zahl 1 addieren, gibt es auch die geschlossene Form

und es gibt eine verschachtelte Summe quadrierter Fibonacci-Zahlen, die den Kehrwert des Goldenen Schnitts ergeben ,

Die Summe aller geradzahligen reziproken Fibonacci-Zahlen ist

mit der Lambert-Serie     seit  

Die reziproke Fibonacci-Konstante ist also

Darüber hinaus wurde diese Zahl von Richard André-Jeannin als irrational bewiesen .

Die Millin-Serie gibt die Identität

die aus der geschlossenen Form für ihre Teilsummen folgt, da N gegen Unendlich strebt:

Primzahlen und Teilbarkeit

Teilbarkeitseigenschaften

Jede dritte Zahl der Folge ist gerade und allgemeiner gesagt ist jede k- te Zahl der Folge ein Vielfaches von F k . Somit ist die Fibonacci-Folge ein Beispiel für eine Teilbarkeitsfolge . Tatsächlich erfüllt die Fibonacci-Folge die stärkere Teilbarkeitseigenschaft

Drei aufeinanderfolgenden Fibonacci - Zahlen sind paarweise coprime , was bedeutet , daß für jedes n ,

gcd ( F n , F n + 1 ) = gcd ( F n , F n + 2 ) = gcd ( F n + 1 , F n + 2 ) = 1.

Jede Primzahl p teilt eine Fibonacci - Zahl, die durch den Wert bestimmt werden kann p modulo 5. Wenn p kongruent zu 1 oder 4 (mod 5) ist, dann ist p dividieren F p  - 1 , und wenn p kongruent zu 2 oder 3 (mod 5), dann, p dividieren F p  + 1 . Der verbleibende Fall ist , dass p  = 5, und in diesem Fall p teilt F p .

Diese Fälle können mit dem Legendre-Symbol zu einer einzigen, nicht stückweisen Formel kombiniert werden :

Primzahlprüfung

Die obige Formel kann als Primalitätstest in dem Sinne verwendet werden, dass wenn

wo das Legendre-Symbol durch das Jacobi-Symbol ersetzt wurde , ist dies ein Beweis dafür, dass n eine Primzahl ist, und wenn es nicht gilt, dann ist n definitiv keine Primzahl. Wenn n zusammengesetzt ist und die Formel erfüllt, dann ist n eine Fibonacci-Pseudoprimzahl . Wenn m groß ist – sagen wir eine 500-Bit-Zahl – können wir F m (mod n ) effizient mit der Matrixform berechnen. Daher

Hier ist die Matrix - Leistungs A m wird berechnet unter Verwendung der modularen Potenzierung , die werden können , um Matrizen angepasst .

Fibonacci-Primzahlen

Eine Fibonacci-Primzahl ist eine Fibonacci-Zahl, die eine Primzahl ist . Die ersten sind:

2, 3, 5, 13, 89, 233, 1597, 28657, 514229, ... OEISA005478 .

Fibonacci-Primzahlen mit Tausenden von Stellen wurden gefunden, aber es ist nicht bekannt, ob es unendlich viele gibt.

F kn ist durch F n teilbar , daher muss jede Fibonacci-Primzahl außer F 4 = 3 einen Primindex haben. Da es beliebig lange Reihen zusammengesetzter Zahlen gibt, gibt es also auch beliebig lange Reihen zusammengesetzter Fibonacci-Zahlen.

Keine Fibonacci-Zahl größer als F 6 = 8 ist um eins größer oder kleiner als eine Primzahl.

Die einzige nichttriviale quadratische Fibonacci-Zahl ist 144. Attila Pethő bewies 2001, dass es nur endlich viele Fibonacci-Zahlen mit perfekter Potenz gibt. 2006 bewiesen Y. Bugeaud, M. Mignotte und S. Siksek, dass 8 und 144 die einzigen nicht-trivialen perfekten Potenzen sind.

1, 3, 21, 55 sind die einzigen dreieckigen Fibonacci-Zahlen, die von Vern Hoggatt vermutet und von Luo Ming bewiesen wurden.

Keine Fibonacci-Zahl kann eine perfekte Zahl sein . Im Allgemeinen kann keine andere Fibonacci-Zahl als 1 multipliziert perfekt sein , und kein Verhältnis von zwei Fibonacci-Zahlen kann perfekt sein.

Primteiler

Mit Ausnahme von 1, 8 und 144 ( F 1 = F 2 , F 6 und F 12 ) hat jede Fibonacci-Zahl einen Primfaktor, der kein Faktor einer kleineren Fibonacci-Zahl ist ( Theorem von Carmichael ). Folglich sind 8 und 144 ( F 6 und F 12 ) die einzigen Fibonacci-Zahlen, die das Produkt anderer Fibonacci-Zahlen OEISA235383 sind .

Die Teilbarkeit der Fibonacci-Zahlen durch eine Primzahl p hängt mit dem Legendre-Symbol zusammen, das wie folgt ausgewertet wird:

Wenn p eine Primzahl ist, dann

Zum Beispiel,

Es ist nicht bekannt, ob es eine Primzahl p gibt, so dass

Solche Primzahlen (sofern es welche gibt) werden Wand-Sonne-Sonne-Primzahlen genannt .

Wenn p ≠ 5 eine ungerade Primzahl ist, dann gilt:

Beispiel 1. p = 7, in diesem Fall p ≡ 3 (mod 4) und wir haben:

Beispiel 2. p = 11, in diesem Fall p ≡ 3 (mod 4) und wir haben:

Beispiel 3. p = 13, in diesem Fall p ≡ 1 (mod 4) und wir haben:

Beispiel 4. p = 29, in diesem Fall p ≡ 1 (mod 4) und wir haben:

Für ungerade n sind alle ungeraden Primteiler von F n kongruent zu 1 modulo 4, was impliziert, dass alle ungeraden Teiler von F n (als Produkte von ungeraden Primteilern) kongruent zu 1 modulo 4 sind.

Zum Beispiel,

Alle bekannten Faktoren der Fibonacci-Zahlen F ( i ) für alle i < 50000 werden in den entsprechenden Depots gesammelt.

Periodizität modulo n

Wenn die Mitglieder der Fibonacci-Folge mod  n genommen werden , ist die resultierende Folge periodisch mit einer Periode von höchstens  6n . Die Längen der Perioden für verschiedene n bilden die sogenannten Pisano-Perioden OEISA001175 . Die Bestimmung einer allgemeinen Formel für die Pisano-Perioden ist ein offenes Problem, das als Teilproblem eine spezielle Instanz des Problems des Findens der multiplikativen Ordnung einer modularen ganzen Zahl oder eines Elements in einem endlichen Körper enthält . Für jedes bestimmte n kann jedoch die Pisano-Periode als ein Beispiel für die Zykluserkennung gefunden werden .

Größe

Da F n ist asymptotisch an , die Anzahl der Stellen in F n ist asymptotisch zu . Folglich gibt es für jede ganze Zahl d > 1 entweder 4 oder 5 Fibonacci-Zahlen mit d Dezimalstellen.

Allgemeiner ausgedrückt ist in der Darstellung zur Basis b die Anzahl der Stellen in F n asymptotisch zu

Verallgemeinerungen

Die Fibonacci-Folge ist eine der einfachsten und frühesten bekannten Folgen, die durch eine Wiederholungsbeziehung und insbesondere durch eine lineare Differenzengleichung definiert wird . Alle diese Folgen können als Verallgemeinerungen der Fibonacci-Folge angesehen werden. Insbesondere kann Binets Formel auf jede Folge verallgemeinert werden, die eine Lösung einer homogenen linearen Differenzengleichung mit konstanten Koeffizienten ist.

Einige spezifische Beispiele, die in gewisser Weise der Fibonacci-Folge nahe kommen, sind:

  • Verallgemeinerung des Index auf negative ganze Zahlen, um die Negafibonacci- Zahlen zu erzeugen .
  • Verallgemeinerung des Index auf reelle Zahlen unter Verwendung einer Modifikation der Binet-Formel.
  • Beginnend mit anderen ganzen Zahlen. Lucas-Zahlen haben L 1 = 1, L 2 = 3 und L n = L n −1 + L n −2 . Primefree Sequenzen verwenden , um die Fibonacci - Rekursion mit anderen Ausgangspunkt Sequenzen zu erzeugen , in denen alle Zahlen sind Verbunde .
  • Lassen Sie eine Zahl eine lineare Funktion (anders als die Summe) der 2 vorhergehenden Zahlen sein. Die Pell-Zahlen haben P n = 2 P n − 1 + P n − 2 . Wird dem Koeffizienten des vorhergehenden Wertes ein variabler Wert x zugewiesen , ergibt sich die Folge von Fibonacci-Polynomen .
  • Die unmittelbar vorangehenden Zahlen werden nicht hinzugefügt. Die Padovan-Folge und die Perrin-Zahlen haben P ( n ) = P ( n − 2) + P ( n − 3).
  • Generieren der nächsten Zahl durch Addieren von 3 Zahlen (Tribonacci-Zahlen), 4 Zahlen (Tetranacci-Zahlen) oder mehr. Die resultierenden Folgen werden als n-Schritt-Fibonacci-Zahlen bezeichnet .

Anwendungen

Mathematik

Die Fibonacci-Zahlen sind die Summen der "flachen" Diagonalen (in Rot dargestellt) des Pascalschen Dreiecks .

Die Fibonacci-Zahlen treten in den Summen der "flachen" Diagonalen im Pascalschen Dreieck auf (siehe Binomialkoeffizient ):

Die erzeugende Funktion kann erweitert werden in

und sammeln wie begriffe von , wir haben die identität

Um zu sehen, wie die Formel verwendet wird, können wir die Summen nach der Anzahl der vorhandenen Terme anordnen:

5 = 1+1+1+1+1
= 2+1+1+1 = 1+2+1+1 = 1+1+2+1 = 1+1+1+2
= 2+2+1 = 2+1+2 = 1+2+2

das heißt , wo wir die Positionen von k zweien aus nk-1 Termen wählen .

Verwendung der Fibonacci-Folge zum Zählen von {1, 2}-eingeschränkten Kompositionen

Diese Zahlen geben auch die Lösung bestimmter Aufzählungsprobleme, von denen das häufigste darin besteht, die Anzahl der Schreibweisen einer gegebenen Zahl n als geordnete Summe von 1 und 2 zu zählen ( Kompositionen genannt ); es gibt F n +1 Möglichkeiten, dies zu tun (entsprechend ist es auch die Anzahl der Dominosteine des Rechtecks). Zum Beispiel gibt es F 5+1 = F 6 = 8 Möglichkeiten, eine Treppe mit 5 Stufen zu erklimmen, indem man eine oder zwei Stufen gleichzeitig macht:

5 = 1+1+1+1+1 = 2+1+1+1 = 1+2+1+1 = 1+1+2+1 = 2+2+1
= 1+1+1+2 = 2+1+2 = 1+2+2

Die Abbildung zeigt, dass 8 in 5 (die Anzahl der Aufstiegswege für 4 Stufen, gefolgt von einem Einzelschritt) plus 3 (die Anzahl der Aufstiegswege für 3 Stufen, gefolgt von einem Doppelschritt) zerlegt werden kann. Die gleiche Argumentation wird rekursiv bis zu einer einzigen Stufe angewendet , von der es nur einen Aufstiegsweg gibt.

Die Fibonacci-Zahlen können auf unterschiedliche Weise in der Menge der binären Strings oder äquivalent in den Teilmengen einer gegebenen Menge gefunden werden.

  • Die Anzahl der Binärstrings der Länge n ohne aufeinanderfolgende 1 s ist die Fibonacci-Zahl F n +2 . Zum Beispiel aus den 16 binären Strings der Länge 4 ist F 6 = 8 , ohne aufeinanderfolgende 1 s - sie sind 0000, 0001, 0010, 0100, 0101, 1000, 1001 und 1010. In äquivalentem, F n + 2 ist , die Anzahl der Teilmengen Svon {1, ..., n } ohne aufeinanderfolgende ganze Zahlen, dh diejenigen S, für die { i , i + 1} ⊈ S für jedes i . Eine Bijektion mit den Summen zu n+1 besteht darin, 1 durch 0 und 2 durch 10 zu ersetzen und die letzte Null wegzulassen.
  • Die Anzahl der Binärstrings der Länge n ohne ungerade Anzahl aufeinanderfolgender 1 s ist die Fibonacci-Zahl F n+1 . Zum Beispiel gibt es von den 16 Binärstrings der Länge 4 F 5 = 5 ohne eine ungerade Anzahl aufeinanderfolgender 1 s – sie sind 0000, 0011, 0110, 1100, 1111. Entsprechend ist die Anzahl der Teilmengen S von {1 , ..., n } ohne ungerade Anzahl aufeinanderfolgender Ganzzahlen ist F n +1 . Eine Bijektion mit den Summen zu n besteht darin, 1 durch 0 und 2 durch 11 zu ersetzen .
  • Die Anzahl der Binärstrings der Länge n ohne eine gerade Anzahl aufeinanderfolgender 0 s oder 1 s beträgt 2 F n . Zum Beispiel gibt es von den 16 Binärstrings der Länge 4 2 F 4 = 6 ohne eine gerade Anzahl aufeinanderfolgender 0 s oder 1 s – das sind 0001, 0111, 0101, 1000, 1010, 1110. Es gibt ein Äquivalent Aussage über Teilmengen.
  • Yuri Matiyasevich konnte zeigen, dass die Fibonacci-Zahlen durch eine diophantische Gleichung definiert werden können , was zur Lösung des zehnten Problems von Hilbert führte .
  • Die Fibonacci-Zahlen sind auch ein Beispiel für eine vollständige Folge . Dies bedeutet, dass jede positive ganze Zahl als Summe von Fibonacci-Zahlen geschrieben werden kann, wobei jede Zahl höchstens einmal verwendet wird.
  • Darüber hinaus kann jede positive ganze Zahl auf einzigartige Weise als Summe einer oder mehrerer verschiedener Fibonacci-Zahlen so geschrieben werden, dass die Summe keine zwei aufeinanderfolgenden Fibonacci-Zahlen enthält. Dies ist als Satz von Zeckendorf bekannt , und eine Summe von Fibonacci-Zahlen, die diese Bedingungen erfüllt, wird als Zeckendorf-Darstellung bezeichnet. Die Zeckendorf-Darstellung einer Zahl kann verwendet werden, um ihre Fibonacci-Codierung abzuleiten .
  • Beginnend mit 5 ist jede zweite Fibonacci-Zahl die Länge der Hypotenuse eines rechtwinkligen Dreiecks mit ganzzahligen Seiten, oder anders ausgedrückt, die größte Zahl in einem pythagoräischen Tripel , erhalten aus der Formel
    Die aus dieser Formel erhaltene Folge von pythagoräischen Dreiecken hat Seitenlängen (3,4,5), (5,12,13), (16,30,34), (39,80,89), ... Die mittlere Seite jedes dieser Dreiecke ist die Summe der drei Seiten des vorhergehenden Dreiecks.
  • Der Fibonacci-Würfel ist ein ungerichteter Graph mit einer Fibonacci-Knotenzahl, der als Netzwerktopologie für paralleles Rechnen vorgeschlagen wurde .
  • Fibonacci-Zahlen erscheinen im Ringlemma , das verwendet wird, um Verbindungen zwischen dem Kreispackungssatz und konformen Abbildungen zu beweisen .

Informatik

Fibonacci-Baum der Höhe 6. Gleichgewichtsfaktoren grün; Höhen rot.
Die Schlüssel im linken Rücken sind Fibonacci-Zahlen.

Natur

Gelber Kamillenkopf mit der Anordnung in 21 (blau) und 13 (aqua) Spiralen. Solche Anordnungen mit aufeinanderfolgenden Fibonacci-Zahlen kommen in einer Vielzahl von Pflanzen vor.

Fibonacci-Sequenzen treten in biologischen Umgebungen auf, z. B. bei der Verzweigung von Bäumen, der Anordnung von Blättern an einem Stiel , den Früchten einer Ananas , der Blüte einer Artischocke , einem sich entfaltenden Farn und der Anordnung eines Tannenzapfens und dem Stammbaum der Honigbiene. Kepler wies auf das Vorkommen der Fibonacci-Folge in der Natur hin und erklärte damit die (mit dem Goldenen Schnitt zusammenhängende) fünfeckige Form einiger Blumen. Feld Gänseblümchen haben am häufigsten Blütenblätter in Zählungen der Fibonacci - Zahlen. 1754 entdeckte Charles Bonnet , dass die spiralförmige Phyllotaxis von Pflanzen häufig in Fibonacci-Zahlenreihen ausgedrückt wird.

Przemysław Prusinkiewicz vertrat die Idee, dass reale Instanzen teilweise als Ausdruck bestimmter algebraischer Beschränkungen freier Gruppen verstanden werden können , insbesondere als bestimmte Lindenmayer-Grammatiken .

Illustration des Vogel-Modells für n = 1 ... 500

Ein Modell für das Röschenmuster im Kopf einer Sonnenblume wurde 1979 von Helmut Vogel vorgeschlagen . Dieses hat die Form

wobei n die Indexnummer der Blüte ist und c ein konstanter Skalierungsfaktor ist; die Röschen liegen also auf der Fermatschen Spirale . Der Divergenzwinkel, ungefähr 137,51°, ist der goldene Winkel , der den Kreis im goldenen Schnitt teilt. Da dieses Verhältnis irrational ist, hat kein Röschen einen Nachbarn im exakt gleichen Winkel von der Mitte, sodass sich die Röschen effizient packen. Da die rationalen Näherungen an den Goldenen Schnitt die Form F ( j ): F ( j + 1) haben , sind die nächsten Nachbarn der Blütenzahl n die bei n ± F ( j ) für einen Index j , der von r abhängt , die Entfernung vom Zentrum. Sonnenblumen und ähnliche Blumen haben am häufigsten Spiralen von Blüten im Uhrzeigersinn und gegen den Uhrzeigersinn in der Höhe benachbarter Fibonacci-Zahlen, die normalerweise durch den äußersten Bereich von Radien gezählt werden.

Fibonacci-Zahlen erscheinen auch in den Ahnentafeln idealisierter Honigbienen nach den folgenden Regeln:

  • Wird ein Ei von einem ungepaarten Weibchen gelegt, schlüpft daraus ein Männchen oder eine Drohnenbiene .
  • Wurde jedoch ein Ei von einem Männchen befruchtet, schlüpft daraus ein Weibchen.

So hat eine männliche Biene immer einen Elternteil und eine weibliche Biene zwei. Wenn man den Stammbaum einer männlichen Biene (1 Biene) verfolgt, hat sie 1 Elternteil (1 Biene), 2 Großeltern, 3 Urgroßeltern, 5 Ururgroßeltern und so weiter. Diese Zahlenfolge der Eltern ist die Fibonacci-Folge. Die Anzahl der Vorfahren auf jeder Ebene, F n , ist die Anzahl der weiblichen Vorfahren, die F n –1 ist , plus die Anzahl der männlichen Vorfahren, die F n –2 beträgt . Dies geschieht unter der unrealistischen Annahme, dass die Vorfahren auf jeder Ebene ansonsten nicht miteinander verwandt sind.

Die Anzahl der möglichen Vorfahren auf der Vererbungslinie des X-Chromosoms bei einer bestimmten Ahnengeneration folgt der Fibonacci-Sequenz. (Nach Hutchison, L. "Der Stammbaum wachsen: Die Macht der DNA bei der Rekonstruktion von Familienbeziehungen".)

Es wurde festgestellt, dass die Anzahl möglicher Vorfahren auf der Vererbungslinie des menschlichen X-Chromosoms bei einer bestimmten Ahnengeneration ebenfalls der Fibonacci-Sequenz folgt. Ein männliches Individuum hat ein X-Chromosom, das er von seiner Mutter erhalten hat, und ein Y-Chromosom , das er von seinem Vater erhalten hat. Das Männchen gilt als "Ursprung" seines eigenen X-Chromosoms ( ), und in der Generation seiner Eltern stammte sein X-Chromosom von einem alleinerziehenden Elternteil ( ). Die Mutter des Mannes erhielt ein X-Chromosom von ihrer Mutter (der Großmutter mütterlicherseits des Sohns) und eines von ihrem Vater (dem Großvater mütterlicherseits des Sohns), sodass zwei Großeltern zum X-Chromosom des männlichen Nachkommens beigetragen haben ( ). Der Großvater mütterlicherseits erhielt sein X-Chromosom von seiner Mutter, und die Großmutter mütterlicherseits erhielt X-Chromosomen von beiden Elternteilen, so dass drei Urgroßeltern zum X-Chromosom des männlichen Nachkommens beigetragen haben ( ). Fünf Ururgroßeltern trugen zum X-Chromosom des männlichen Nachkommens bei ( ), usw. (Dies setzt voraus, dass alle Vorfahren eines bestimmten Nachkommens unabhängig sind, aber wenn eine Genealogie weit genug zurückverfolgt wird, beginnen Vorfahren auf mehreren Linien zu erscheinen der Genealogie, bis schließlich ein Populationsgründer auf allen Linien der Genealogie auftaucht.)

Die Wege von Tubulinen auf intrazellulären Mikrotubuli ordnen sich in Mustern von 3, 5, 8 und 13 an.

Sonstiges

  • Wenn in der Optik ein Lichtstrahl schräg durch zwei gestapelte transparente Platten aus verschiedenen Materialien mit unterschiedlichen Brechungsindizes scheint , kann er von drei Oberflächen reflektiert werden: der oberen, mittleren und unteren Oberfläche der beiden Platten. Die Anzahl der verschiedenen Strahlengänge mit k Reflexionen für k > 1 ist die te Fibonacci-Zahl. (Wenn jedoch k = 1 ist , gibt es drei Reflexionspfade, nicht zwei, sondern einen für jede der drei Oberflächen.)
  • Fibonacci-Retracement- Level werden häufig in der technischen Analyse für den Finanzmarkthandel verwendet.
  • Da der Umrechnungsfaktor 1,609344 für Meilen in Kilometer nahe am Goldenen Schnitt liegt, wird die Zerlegung der Entfernung in Meilen in eine Summe von Fibonacci-Zahlen fast zur Kilometersumme, wenn die Fibonacci-Zahlen durch ihre Nachfolger ersetzt werden. Dieses Verfahren läuft darauf hinaus, dass ein Radix- 2- Zahlenregister in der Basis des Goldenen Schnitts φ verschoben wird. Um von Kilometern in Meilen umzurechnen, verschieben Sie stattdessen das Register in der Fibonacci-Folge nach unten.
  • Braschet al. 2012 zeigen, wie eine verallgemeinerte Fibonacci-Folge auch mit dem Gebiet der Wirtschaftswissenschaften verbunden werden kann. Insbesondere wird gezeigt, wie eine verallgemeinerte Fibonacci-Folge mit einem Zustand und einer Kontrollvariablen in die Kontrollfunktion von endlichen Horizont-Optimierungsproblemen eingeht. Das Verfahren wird an einem Beispiel veranschaulicht, das oft als Brock-Mirman-Wirtschaftswachstumsmodell bezeichnet wird.
  • Mario Merz hat die Fibonacci-Folge ab 1970 in einige seiner Kunstwerke aufgenommen.
  • Joseph Schillinger (1895–1943) entwickelte ein Kompositionssystem, das in einigen seiner Melodien Fibonacci-Intervalle verwendet; er betrachtete diese als das musikalische Gegenstück zu der kunstvollen Harmonie, die sich in der Natur zeigt. Siehe auch Goldener Schnitt § Musik .

Siehe auch

Verweise

Fußnoten

Zitate

zitierte Werke

Externe Links