Fibonnacci-számok, lineáris rekurzió, racionális generátorfüggvények

Tegyük fel, hogy nyúlpárok együtt születnek és egy családot alkotnak az alábbi biológiai törvények szerint: A párok életük első hónapja után érik el az ivarérettséget és a második hónaptól kezdve minden hónapban egy nyúlpárnak adnak életet. Kapunk egy újszülött nyúlpárt. További nyulakat nem kapunk, a nyulaink nem hullanak el. hány nyúlpárunk lesz egy évvel, vagy általában n hónappal az ajándékozott pár megkapása után. Legyen Fn a fenti kérdésre adott válasz.

Nyilván F0=F1=1. Két hónap múlva azonban megszületik az első nyúlpárunk, F2=2. A harmadik hónapban újabb nyúlpár születik, F3=3. A negyedik hónapban újabb nyúlpárja születik az eredeti párnak. Ezzel egyidőben, legidősebb nyúlpáruk megszüli az eredeti pár első unokapárját, F4=5.

Definíció: A bevezető feladat által definiált sorozatot Fibonacci-sorozatnak, elemeit Fibonacci-számoknak nevezzük.

Lemma: n>=2 esetén Fn=Fn-1+Fn-2.

A Fibonacci-számok a matematikai sorozatok egyik legismertebbje. A legkülönbözőbb területeken (művészetek, természet...) előfordulnak és a népszerúsítő matematikai irodalom kedvelt témája. A számsorozat elnevezését Leonardo Pisano Fibonacci matematikusról kapta.

Az alábbiakban néhány interneten elérhető honlapot adunk közre, amleyek a Fibonacci-számokkal kapcsolatosak.

Végül megemlítünk egy fejtörőt. Ez egy link egy geometria fejtörőhöz, amelyhez ábra tartozik. Az ábrán ismerjünk fel Fibonacci-számokat. Véletlen a Fibonacci-számok ilyen ``burjánzása ''?


A Fibonacci-számok és a generátorfuggvény módszer

Legyen F(x)=F0+F1x+F2x2F3x3+...

F(x) együtthatói kielégítik a Fibonacci-számokra vonatkozó rekurziót (hiszen azok a Fibonacci-számok) de az Fn-re vonatkozó egyenlőségben szereplő együtthatók különböző x hatványok együtthatói. A következő trükkel három formális hatványsort írunk fel, hogy a három xn-együttható éppen a rekurzió által leírt módon viszonyul egymáshoz.

Így az utolsó két formális hatványsor összegében a rekurzió érvényességének körében (n>=2 esetén) F(x) együtthatói adódnak.

A kezdeti együtthatók eltérését könnyen korrigálhatjuk:

Ebből adódik, hogy F(x)=1/(1-x-x2). A hányados nevezőjét szorzattá alakíthatjuk:

A nevező első tényezőjét jelöljük N1-gyel, a második tényezőjét N2-vel. A két kifejezés összege és külonbsége egyszerűen felírható:

Ezalapján a számláló is kifejezhető a nevező tényezőiből.

Ebből pedig adódik F(x) parciális törtekre bontása:


A fenti módszer egy alternatív (angol nyelvű) tárgyalását Fibonacci Numbers Spelled Out honlap tárgyalja.