Fibonacciluvut

Fibonacciluvut ovat lukujono, jossa F0 = 0, F1 = 1 ja Fn = Fn-1 + Fn-2 kaikille n ≥ 2. Jokainen termi on kahden edeltäjän summa, ja sarja muodostaa kokonaisluvuista koostuvan, nopeasti kasvavan järjestelmän.

Binetin kaavan mukaan Fn = (φ^n − ψ^n)/√5, missä φ = (1+√5)/2 on kultainen suhde ja ψ = (1−√5)/2. Luvut kasvavat eksponentiaalisesti: Fn on likimäärin φ^n/√5, ja peräkkäisten termien suhde Fn+1/Fn lähestyy φ.

Fibonacciluvut esiintyvät laajasti sekä teoreettisessa että sovelletussa matematiikassa. Ne liittyvät erilaisten tilasovellusten ratkaisuun sekä rekursiivisiin ratkaisuihin, esimerkiksi n:n pituista ruudukkoa kattavissa ratkaisuissa käytetään 1×1 ja 1×2 palikoita. Zeckendorfin teoreeman mukaan jokainen positiivinen kokonaisluku voidaan esittää yksikertaisena summana ei-vierekkäisistä Fibonacci-luvuista, mikä antaa ainutlaatuisen esitystavan.

Historia: Nimi viittaa italialaiseen matemaatikko Leonardo Fibonacciin, joka toi luvut länsimaiseen matematiikkaan teoksessaan Liber Abaci (1202). Luvut olivat tunnettuja myös ennen tätä ja niitä on käsitelty eri kulttuureissa, mutta Fibonaccian kautta ne saivat laajan huomion.

Nykykäytössä fibonaccilukuja sovelletaan muun muassa algoritmeihin ja dynaamiseen ohjelmointiin. Ne ilmentävät kasvua luonnossa ja toimivat keskeisenä esimerkkinä toistorakenteista sekä rekursiivisista ratkaisuista.