Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

1.10. A Fibonacci számok

1.10. A Fibonacci számok

1.23. Definíció. Fibonacci sorozat

Fibonacci számsorozatnak nevezzük azt az számsorozatot, amelyet az alábbi formulapár határoz meg:

A 1.2 és 1.3 formulapár által előállított számok sorozata így kezdődik:

A probléma a fenti definícióval az, hogy az indexű elemet nem tudjuk a megelőzőek nélkül kiszámítani a rekurziós formula alapján. Mennyi például -nak az értéke? Ennek a problémának a megoldását adja a Binet formula.

1.24. Tétel. Binet formula

A Fibonacci számsorozat elemei felírhatók az index függvényében az alábbi úgynevezett Binet formula révén:

ahol

Bizonyítás. Keresnünk kell olyan számsorozatot, amely az 1.2, 1.3 feltételeknek megfelel. Könnyebb lesz a dolgunk, ha egyelőre az 1.2 feltételtől eltekintünk. A trükk: keressünk olyan sorozatokat, amelyek tudják a 1.3 tulajdonságot és alakjuk valamilyen számra. A megoldások közül zárjuk ki a z=0 esetet, mint érdektelent, hiszen ez csupa zérust ad és az nekünk biztosan nem jó. A 1.3 tulajdonságot felírva -re

adódik, ahonnan -nel leosztva a

összefüggésre jutunk. Ennek a másodfokú egyenletnek két valós megoldása van: és . Tehát az megoldás. Könnyen meggyőződhetünk behelyettesítéssel 1.3-be, hogy akkor az is megoldás, ahol tetszőleges konstans. Ugyanígy mivel megoldás, akkor is az. Itt szintén tetszőleges konstans. Azt kaptuk, hogy a megoldások konstansszorosai is megoldások. Vegyük észre továbbá, hogy az

is megoldás.

Összegezve: a és a úgynevezett alapmegoldások (bázismegoldások) lineáris kombinációi is megoldást adnak. Helyettesítsük be 1.7-ot 1.2-be az és esetre. Ezzel csempésszük vissza a kezdetben elhanyagolt 1.2 feltételt. Az alábbi kétismeretlenes, két egyenletből álló lineáris egyenletrendszert kapjuk, melyben az ismeretlenek és .

Innen -et és -t kifejezve kapjuk, hogy

1.25. Tétel. A Fibonacci számok előállítása kerekítéssel

Az Fibonacci szám képezhető az alábbi módon a Binet formula felhasználásával:

Bizonyítás. Belátjuk, hogy és között kevesebb, mint az eltérés. Ez azt jelenti, hogy a kerekítendő szám köré fel tudunk rajzolni egy szimmetrikus intervallumot, amelynek a szélessége kevesebb, mint egy. Ekkor azonban csak egyetlen egész szám lehet ebben az intervallumban, ami így szükségszerűen éppen a Fibonacci szám lesz.

Ugyanis és . Tehát

amiből látszik, hogy egybeesik az egyetlen egésszel, amely a megadott intervallumban van.

A Fibonacci számok sorozata exponenciálisan növekszik. Ez következik a előállításból.

Írhatjuk, hogy