Fibonaccin luvut ovat matematiikan lukujono, joka on nimetty Fibonaccina tunnetun Pisan Leonardon mukaan. Fibonacci kirjoitti vuonna 1202 kirjan nimeltä Liber Abaci ("Laskentakirja"), joka esitteli numerokuvion länsieurooppalaiseen matematiikkaan, vaikka intialaiset matemaatikot tiesivät siitä jo aiemmin.

Kuvion ensimmäinen luku on 0, toinen luku on 1, ja jokainen sen jälkeinen luku on yhtä suuri kuin kahden sitä edeltävän luvun yhteenlaskeminen. Esimerkiksi 0+1=1 ja 3+5=8. Tämä sarja jatkuu loputtomiin.

Tämä voidaan kirjoittaa toistosuhteena,

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}}

Jotta tämä olisi järkevää, on annettava ainakin kaksi lähtökohtaa. Tässä F 0 = 0 {\displaystyle F_{0}=0}{\displaystyle F_{0}=0} ja F 1 = 1 {\displaystyle F_{1}=1}{\displaystyle F_{1}=1} .

Määritelmä ja ensimmäiset luvut

Fibonaccin lukujono (F_n) määritellään rekursiivisesti seuraavasti: F_n = F_{n-1} + F_{n-2} kaikilla n ≥ 2, ja lähtöarvot ovat yleensä F_0 = 0 ja F_1 = 1. Näin syntyy sarja:

  • F_0 = 0
  • F_1 = 1
  • F_2 = 1
  • F_3 = 2
  • F_4 = 3
  • F_5 = 5
  • F_6 = 8
  • F_7 = 13
  • F_8 = 21
  • F_9 = 34
  • F_10 = 55

Suljettu kaava (Binetin kaava)

Fibonaccin luvuille on olemassa suljettu kaava, joka ei käytä rekursiota. Tämän kutsutaan Binetin kaavaksi:

F_n = (phi^n - psi^n) / sqrt(5),

missä phi = (1 + sqrt(5)) / 2 on niin sanottu kultainen luku ja psi = (1 - sqrt(5)) / 2 sen konjugaatti. Koska |psi| < 1, psi^n pienenee nopeasti, joten suurille n:ille F_n on käytännössä lähinnä phi^n / sqrt(5).

Kultainen leikkaus

Fibonaccin lukujen suhteet lähestyvät vakioa, jota kutsutaan kultaiseksi leikkaukseksi. Kun n kasvaa, suhde F_{n+1}/F_n → phi ≈ 1,6180339887.... Tämä piirre tekee lukujonosta yhteydessä geometriaan, taiteeseen ja luonnon muodostelmiin.

Ominaisuuksia ja identiteettejä

  • Summa: F_0 + F_1 + ... + F_n = F_{n+2} − 1.
  • Kaikilla n pätee F_{n+k} = F_k F_{n+1} + F_{k-1} F_n (Cassiniin liittyvät identiteetit ovat erityistapauksia).
  • Cassinin identiteetti: F_{n+1} F_{n-1} − F_n^2 = (−1)^n.
  • Fibonaccin luvut voidaan esittää myös 2×2-matriisin potenssina:
    [ [1,1],[1,0] ]^n = [ [F_{n+1}, F_n], [F_n, F_{n-1}] ].
  • Generaattorifunktio: G(x) = x / (1 − x − x^2), josta voi johtaa monia sarjaominaisuuksia.
  • Modulon mukaan kyseessä on jaksollinen sarja — Pisano-jakso kertoo, millä periodilla Fibonaccin luvut toistuvat modulo m.

Sovelluksia ja esiintymistä luonnossa

Fibonaccin luvut esiintyvät monissa luonnonilmiöissä ja ihmisen tekemissä rakenteissa:

  • Kasvien lehtien, kukkavarsien ja käpyjen muodostumismallit
  • Perhosen siipien ja lehtien asetelmien laskennallinen mallintaminen
  • Tietojenkäsittelytiede: rekursiiviset algoritmit, dynaaminen ohjelmointi ja hakupuut
  • Kuvataide ja arkkitehtuuri: kultaisen leikkauksen käyttö suhdeluvuissa

Laskeminen käytännössä

Vaikka rekursiivinen määritelmä on yksinkertainen, suora rekursiivinen laskenta on tehottomaa (paljon päällekkäislaskentaa). Käytännössä kannattavampia tapoja ovat:

  • Dynaaminen ohjelmointi (iteratiivinen laskenta tai muistin käyttö välitulosten säilyttämiseen).
  • Matriisipotenssit tai binääriin eksponentointi matriisilla, joka antaa O(log n) monimutkaisuuden.
  • Binetin kaavan käyttäminen liukulukulaskennassa suurilla n:illä (huomioi pyöristysvirheet).

Esimerkkejä ja laskutehtäviä

  • Laske F_12: F_11 = 89, F_12 = F_11 + F_10 = 89 + 55 = 144.
  • Todista, että F_0 + F_1 + ... + F_n = F_{n+2} − 1 käyttäen induktiota.
  • Tutki Fibonaccin lukujen jaksollisuutta modulo 10 (Pisano-jakso modulo 10 on 60).

Fibonaccin lukujono on sekä teoriaa että käytäntöä yhdistävä aihe, jolla on syviä yhteyksiä algebraan, kombinatoriikkaan, lukuteoriaan ja luontoon. Se tarjoaa runsaasti matemaattisia ongelmia ja sovelluksia aloittelijoille ja edistyneemmille tutkijoille.