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: