Fibonaccisekvensen

Fibonaccisekvensen er en talrække, der begynder med 0 og 1, og hvor hvert efterfølgende tal er summen af de to forudgående. I den mest normale form er F_0 = 0, F_1 = 1, og for n ≥ 2 gælder F_n = F_{n-1} + F_{n-2}.Nogle fremstillinger bruger i stedet F_1 = 1 og F_2 = 1; forskellen ligger i indeksationen, ikke i selve reglerne.

Historisk opstod navnet i vestlig matematik gennem Leonardo af Pisa, kendt som Fibonacci, der i værket Liber Abaci (1202) præsenterede rækken i forbindelse med et kanin-problem. Rækken blev hurtigt et centralt eksempel i talteori og rekursion og har siden da optrådt i mange matematiske sammenhænge og anvendelser.

Matematiske egenskaber og variationer: Rækken kan udtrykkes i lukket form ved Binet’s formel: F_n = (φ^n − ψ^n)/√5, hvor φ = (1+√5)/2 og ψ = (1−√5)/2. For store n vokser F_n omtrent som φ^n/√5. Egenskaber inkluderer gcd(F_m, F_n) = F_gcd(m,n) og Zeckendorf’s sætning, som siger at hvert positivt heltal kan udtrykkes som summen af ikke-konsekutive Fibonacci-tal, og denne repræsentation er unik.

Anvendelser og beregning: Den rekursive definition giver nem implementering, men effektiv beregning kræver ofte dynamisk programmering eller avancerede teknikker som fast doubling-metoden, der gør det muligt at beregne F_n i O(log n) tid. I datalogi spiller Fibonaccital ind i data strukturer som Fibonacci-heaps og i søgesammenhænge som Fibonacci-søgninger.

Forekomster i natur og kultur: Rækken dukker op i naturen gennem mønstre i blade og frø (phyllotaksi), i spiralformede arrangementer og i visuelle og kunstneriske sammenhænge. Den bruges også som et klassisk eksempel i undervisning og populærvidenskab.