Fibonacci-talrækken
Binets Formel, Rekursion og Fibonacci i Datalogien
Introduktion: Talrækken som matematisk objekt
Fibonacci-talrækken er let at beskrive rekursivt:
F(0) = 0, F(1) = 1, F(n) = F(n−1) + F(n−2) for n ≥ 2
Men kan man beregne F(n) direkte — uden at kende alle foregående led? Svaret er ja, og det kræver komplekse rødder og det gyldne snit.
Binets Formel
I 1843 udledte den franske matematiker Jacques Philippe Marie Binet en lukket formel:
F(n) = (φⁿ − ψⁿ) / √5
Hvor:
- φ = (1 + √5) / 2 ≈ 1,6180… (det gyldne snit)
- ψ = (1 − √5) / 2 ≈ −0,6180… (den konjugerede rod)
Bemærk: ψ ≈ −0,618, så |ψ|ⁿ → 0 hurtigt. Det betyder:
F(n) = nærmeste heltal til φⁿ / √5
Eksempel: F(10) = nærmeste heltal til φ¹⁰ / √5 = 122,99… / 2,236… ≈ 55 ✓
Udledning (skitseret)
Fibonacci-rekurrensen F(n) = F(n−1) + F(n−2) er en lineær anden-ordens rekurrensligning. Dens karakteristiske ligning er:
x² = x + 1 → x² − x − 1 = 0
Rødderne er φ og ψ. Den generelle løsning er:
F(n) = Aφⁿ + Bψⁿ
Startbetingelserne F(0) = 0 og F(1) = 1 giver A = 1/√5 og B = −1/√5. Indsæt og simplificer → Binets formel.
Fibonacci og Algoritmer: Rekursion vs. Iteration
Naiv rekursiv algoritme
`` fib(n): if n <= 1: return n return fib(n-1) + fib(n-2) ``
Denne algoritme er eksponentielt langsom. For at beregne fib(n) beregner den fib(n−2) to gange, fib(n−4) fire gange, osv. Tidskompleksiteten er O(φⁿ) — dvs. den vokser eksponentielt med n.
Problem: fib(50) kræver ca. 10¹⁰ funktionskald.
Iterativ algoritme
`` fib(n): a, b = 0, 1 for i in range(n): a, b = b, a + b return a ``
Tidskompleksitet: O(n) — lineær. En enorm forbedring.
Matrix-eksponentiering
Fibonacci-talrækken kan udtrykkes som en matrixpotens:
`` [F(n+1)] [1 1]ⁿ [1] [F(n) ] = [1 0] × [0] ``
Med "fast matrix exponentiation" (kvadrering og halvering af eksponent) kan man beregne F(n) på O(log n) multiplikationer — langt hurtigere end den lineære metode.
Oversigt
| Metode | Tidskompleksitet | Velegnet til |
|---|---|---|
| Naiv rekursion | O(φⁿ) ≈ O(1,618ⁿ) | Pædagogisk demonstration |
| Iteration | O(n) | Praktisk brug op til F(10⁶) |
| Binet (floating-point) | O(1) | Approksimation; upræcis for store n |
| Matrix-eksponentiering | O(log n) | Kryptografi, store n |
Fibonacci uden for Matematikken
Datalogi: Fibonacci-heaps bruges i Dijkstras korteste-vej-algoritme. Fibonacci-søgning er en analog til binær søgning.
Biologi: Fyllotaksi — bladarrangement — optimerer lystilgang via den gyldne vinkel 137,5° = 360°/φ².
Finansteori: Fibonacci-retracements (teknisk analyse) bruges til at forudsige prisvendepunkter på markeder. Valide som videnskab? Diskutabelt.
Musikteori: Bartóks strygekvartetter og Debussys Reflets dans l'eau er analyseret som havende Fibonacci-baserede strukturer. Intentionelt? Retrospektiv fortolkning?
Opgave 1 — Binet numerisk
a) Beregn F(15) og F(20) med Binets formel. Verificer mod den rekursive definition.
b) Vis at |ψ|ⁿ < 0,5 for alle n ≥ 1. Hvad betyder dette for præcisionen af afrundingsreglen?
c) For store n introducerer floating-point-aritmetik fejl i Binets formel. For ca. hvilken n-værdi vil en standard 64-bit float (15–17 signifikante cifre) begynde at give forkerte resultater? Begrund dit svar.
Opgave 2 — Algoritmisk analyse
a) Den naive rekursive algoritme beregner fib(5) ved at kalde fib(4) og fib(3). Tegn det fulde kaldtræ for fib(6) og tæl, hvor mange gange fib(2) beregnes.
b) Forklar begrebet memoization: gem allerede beregnede delresultater. Hvad bliver tidskompleksiteten af den naive algoritme med memoization?
c) Matrixformlen giver: [1 1; 1 0]² = [2 1; 1 1], [1 1; 1 0]³ = [3 2; 2 1], [1 1; 1 0]⁴ = [5 3; 3 2]. Bekræft at det øverste venstre element er F(n+1). Hvad er F(7) og F(8) ud fra [1 1; 1 0]⁷?
Opgave 3 — Akademisk refleksion
Fibonacci-talrækken omtales ofte som "naturens eget mønster" og bruges i populariserings-fremstillinger som bevis på matematikens kosmiske karakter.
Skriv en akademisk analyse på 400–600 ord der besvarer:
- Hvad er den matematisk præcise påstand om Fibonacci i naturen (fyllotaksi)? Hvad er evidensen?
- Hvad er de mest citerede eksempler der faktisk er fejlagtige eller overdrevne (fx nautilusskallers spiral)?
- Hvad siger denne tendens til at "overfortolke mønstre" om forholdet mellem matematik og menneskelig kognition?
Analysen skal skelne klart mellem hvad der er dokumenteret, hvad der er fortolkning, og hvad der er myte.
Faglig Fordybelse
Zeckendorf-repræsentation: Ethvert positivt heltal kan entydigt skrives som sum af ikke-sammenhængende Fibonacci-tal (Zeckendorfs sætning, 1972). Eksempel: 100 = 89 + 8 + 3.
Lucas-tal: Sekvensen 2, 1, 3, 4, 7, 11, 18, 29… følger samme rekurrens men med L(0) = 2, L(1) = 1. Forbindelsen: L(n) = F(n−1) + F(n+1). Bruges i Lucas-primtalstest.
Pisano-perioder: F(n) mod m er periodisk for ethvert m. Perioden π(m) kaldes Pisano-perioden. For m = 10: periode 60. For m = 2: periode 3 (0,1,1,0,1,1…). Bruges i kryptografi.
Lærervejledning
Tidsoverblik: Teori Binet + algoritmer 20 min → Opgave 1 15 min → Opgave 2 20 min → Opgave 3 (essay, kan gives som hjemmearbejde) 20 min
Forudsætninger: Eleverne bør kende til andengradsligning, kvadratrødder og gerne basalt programmeringsbegreb.
Differentiering:
- Lettere: Opgave 1a og 2a; opgave 3 som mundtlig drøftelse.
- Sværere: Bevis algebraisk at Fibonacci-rekurrensens karakteristiske ligning giver præcis φ og ψ som rødder, og fuldstændiggør udledningen af Binets formel via startbetingelserne.
Til programmeringsinteresserede: Implementér alle tre algoritmer (naiv rekursion, iteration, memoization) og mål den faktiske køretid for n = 30, 35, 40. Sammenlign med de teoretiske tidskompleksiteter.