Fibonacci-talen är en matematisk talföljd som är uppkallad efter Leonardo av Pisa, känd som Fibonacci. Fibonacci skrev 1202 en bok, Liber Abaci ("Book of Calculation"), som introducerade talmönstret i den västeuropeiska matematiken, även om matematiker i Indien redan kände till det.

Det första talet i mönstret är 0, det andra talet är 1 och varje tal därefter är lika med att lägga ihop de två föregående talen. Till exempel 0+1=1 och 3+5=8. Denna sekvens fortsätter i all oändlighet.

Detta kan skrivas som ett återkommande samband,

F n = F n - 1 + F n - 2 {\displaystyle F_{n}=F_{n-1}+F_{n-2}} {\displaystyle F_{n}=F_{n-1}+F_{n-2}}

För att detta ska bli meningsfullt måste man ta hänsyn till minst två utgångspunkter. Här är F 0 = 0 {\displaystyle F_{0}=0}{\displaystyle F_{0}=0} och F 1 = 1 {\displaystyle F_{1}=1}{\displaystyle F_{1}=1} .

Definition och exempel

Med startvärdena F0 = 0 och F1 = 1 fås följande första termer i sekvensen:

  • F0 = 0
  • F1 = 1
  • F2 = 1 (0 + 1)
  • F3 = 2 (1 + 1)
  • F4 = 3 (1 + 2)
  • F5 = 5 (2 + 3)
  • F6 = 8 (3 + 5)
  • F7 = 13 (5 + 8)
  • F8 = 21 (8 + 13)
  • och så vidare...

Varje nytt tal är alltså summan av de två föregående.

Egenskaper och viktiga formler

  • Binet's formel (sluten form): För n ≥ 0 kan Fn uttryckas med hjälp av det gyllene snittet φ = (1 + √5)/2 och ψ = (1 − √5)/2 som
    Fn = (φ^n − ψ^n) / √5. Denna formel visar att Fn växer ungefär som φ^n / √5 när n blir stort.
  • Gräns för kvoter: Kvoten Fn+1 / Fn konvergerar mot φ när n → ∞. Det är därför Fibonacci-sekvensen är nära kopplad till det gyllene snittet.
  • Genererande funktion: Den formella potensserien G(x) = Σ_{n≥0} Fn x^n har formen G(x) = x / (1 − x − x^2).
  • Matrisform: Man kan använda 2×2-matriser för att generera termer: [ [1,1],[1,0] ]^n = [ [F_{n+1}, F_n],[F_n, F_{n-1}] ]. Detta ger ett snabbt sätt att beräkna Fn med exponentiering via kvadrering.
  • Cassinis identitet: För alla n gäller F_{n+1} F_{n-1} − F_n^2 = (−1)^n.
  • Negativa index: Sekvensen kan utvidgas till negativa index genom återrelationen; man får F_{−n} = (−1)^{n+1} F_n.

Historia och ursprung

Fibonacci introducerade talföljden i västeuropeisk litteratur i Liber Abaci (1202) i samband med en uppgift om reproduktion av kaniner. Men versioner av samma talföljd och relaterade metoder fanns tidigare i indisk matematik, bland annat hos matematikern Virahanka och i verk från 500–1000-talet. Fibonacci populariserade mönstret i Europa, därav namnet.

Tillämpningar och förekomst i naturen

  • Fibonaccital dyker upp i modeller av populationstillväxt, i vissa rekursiva algoritmer och i datastrukturer (t.ex. Fibonacci heap).
  • I naturen syns mönster kopplade till Fibonacci eller det gyllene snittet i arrangemang av blad, frökapslar (t.ex. solros), och spiralformationer hos snäckskal och stormönster.
  • Inom konst och arkitektur används ibland gyllene snittet, som är nära relaterat till Fibonacci-sekvensens kvoter, för proportioner och komposition.

Alternativa startvärden och generaliseringar

Det finns variationer där sekvensen startar med F1 = 1 och F2 = 1 (då blir F0 inte medräknat), men de flesta moderna definitioner använder F0 = 0 och F1 = 1. Man kan också generalisera rekursionsregeln till tribonacci (summa av tre föregående), eller överlag definiera en linjär rekurens av högre ordning.

Beräkning och effektivitet

Att beräkna Fn direkt via den rekursiva definitionen är ineffektivt (exponentiell tidskomplexitet). Effektiva metoder inkluderar:

  • Iterativ beräkning i O(n) tid och O(1) minne.
  • Exponentiering av 2×2-matris med snabb exponentiering (O(log n) multiplikationer).
  • Användning av Binet's formel tillsammans med noggrann flyttalsbehandling eller heltalsapproximationer för stora n.

Sammanfattning

Fibonaccitalen är en grundläggande och välstuderad talföljd inom matematik med tydlig rekursiv definition, rik algebraisk struktur och många praktiska och visuella tillämpningar. Sekvensens koppling till det gyllene snittet och dess förekomst i både teoretiska och naturvetenskapliga sammanhang gör den särskilt intressant.