Fibonacciszámok

Fibonacciszámok egy olyan egész számokból álló sorozat, amelyet a Fn = Fn-1 + Fn-2 rekurzív szabállyal definiálnak n ≥ 2, kezdőértékekkel F0 = 0 és F1 = 1. Egyes kifejezésekben a kezdőértékek F1 = 1 és F2 = 1, ami a konvenciók különbségét adja. Így a sorozat első elemei 0, 1, 1, 2, 3, 5, 8, 13, …

A Fibonacci-sorozat nevét a középkori olasz matematikusról, Leonardo of Pisa (Fibonacci) találmánya adta, amelyet a nyulak szaporodási problémájára adott válaszként vizsgált meg. A sorozatot a matematikában és a számítástudományban széles körben tanulmányozzák.

A számsorozat fontos jellemzői közé tartozik a Fn mod m periódussága a Pisano-periódus szerint. Zárt formát is ismerünk: Fn = (φ^n − ψ^n)/√5, ahol φ = (1 + √5)/2 az arany arány (φ ≈ 1,618...) és ψ = (1 − √5)/2. Nagy n esetén Fn ~ φ^n / √5, azaz a növekedés kvázi exponenciális. Az egymást követő arányok Fn+1/Fn mindinkább a φ-hoz tartanak.

A fiboncciszámok a természetben és a tudományban is megjelennek: például növények elrendeződésében, virágzati mintázatokban és spirális szerkezetekben, illetve a számítástechnikában is használják, például dinamikus programozási példaként vagy a Fibonacci-heap adatszerkezetben. Különböző indexelési konvenciók miatt előfordulhat, hogy F0-val kezdik, vagy F1-től.