2.5 A rekurzív sorozatok

Oldjuk meg a következő - Fibonaccitól származó - feladatot: Egy gazda nyulakat tart. Minden nyúlnak két hónapos korában születik az első kölyke, ezt követően pedig havonta egy-egy. Hány nyúl származik egyetlen pár nyúltól, ha tudjuk, hogy olyan „egyszerűsítő" feltételeket teszünk, hogy a nyulak örökké élnek, és a hím nyulaktól is eltekintünk?

A nyúl állomány létszámát - az első 10 hónapra havi bontásban - a következő táblázatból olvashatjuk le:

Jelőlje Fn a nyulak számát az n-edik hónapban.Ekkor minden n = 2,3,4,... természetes számra fennáll, hogy

Fn = Fn-1 + Fn-2

Az Fi számokat - a feladat kitalálójáról - Fibonacci számoknak nevezzük. Ha a sorozatot kiegészítjük az F0 = 0 számmal, akkor megfigyelhetjük, hogy az  F0 és az F1  számok a Fibonacci sorozatot egyértelműen meghatározzák. Ezért nem szükséges képlettel vagy a korábban ismert függvény megadási definíciókkal megadnunk az összefüggést. Most úgy járunk el, hogy megadjuk a sorozat első néhány tagját, és  megadunk egy szabályt arra vonatkozóan,  hogy a már ismert elemekből hogyan tudjuk kiszámítani a sorozat következő elemét. Azokat a sorozatokat, amelyek így definiálhatók, rekurzív sorozatoknak, az eljárást pedig rekurzív definíciónak nevezzük.

Megjegyzés.

Vegyük észre, hogy a rekurzív definíció rokonságot mutat a teljes indukció gondolatával. Itt azonban nem egy bizonyítási technikáról beszélünk, hanem egy sorozatot adunk meg. (A gondolati rokonságot az adja, hogy itt is azt feltételezzük, hogy a sorozat első n tagja ismert már, és ennek függvényében ki tudjuk számítani az (n+1)-dik tagot. Ezzel tulajdonképpen bármely n-re ki tudjuk számítani a sorozat n-dik tagjának az értékét.)

Teljes indukcióval bebizonyítható a következő tétel.

Tétel. A Fibonacci sorozat elemeire fennáll a következő azonosság: