Fibonacci sorozat

Ezt a sorozatot az olasz Fibonacci-ról nevezték el, mert ő fogalmazta meg a következő feladatot:

"Hány pár nyúl származhat egy évben egyetlen pártól, ha minden pár havonta új párnak ad életet, amely a második hónaptól lesz tenyészképes, és feltételezzük, hogy egy ivadék sem pusztul el?"

A válasz a következő sorozat: 1, 1, 2, 3, 5, stb. Azaz h1=1, h2=1, h3=2, h4=3, h5=5, stb. tehát az első két hónapban (h1, h2) még csak a "kezdő" párunk van, a harmadik hónapban születik meg az első új pár. A negyedik hónapban ez az új pár még nem ellik, de szülei igen, így már három pár nyúlunk van. És így tovább.

Általánosítva: Fibonacci sorozatoknak nevezzük azokat a sorozatokat, amelyeknél az első két tag adott, ezt követően minden tag az őt megelőző két tag összege.

Formulával: adott a1 és a2, és an=an-1+an-2.

Fibonacci sorozathoz jutunk akkor, ha azt számoljuk, hogy egy lépcsőn felfelé haladva hányféleképpen juthatunk fel az n-edik lépcsőfokra, ha feltételezzük, hogy egyszerre csak egy, de legfeljebb két lépcsőfokot tudunk lépni.

Tekintsük a kiindulási helyzetünket az első lépcsőfoknak. Ez az első tagja a sorozatnak, a1=1. A második lépcsőre lépni csak egy lehetőségünk van, nevezetesen a kiindulási pontról, ezért a2=1. A harmadik lépcsőre kétféleképpen juthatunk fel, a kiindulási pontról és az második lépcsőről, tehát a3=2. A negyedik lépcsőre a harmadikról vagy a másodikról juthatunk. A másodikra 1, a harmadikra 2, így a megyedikre 3 lehetőségünk van. És így tovább. A mellékelt ábrán a lépcsők alatti számok mutatják, hogy arra lépcsőfokra hány lehetőségünk van feljutni.

A sorozat szemléltetésére szokták még a következő példát mondani:

Egy fa az ültetést követő második évben hoz először új ágat. Minden ág a keletkezését követő évben csak gyarapszik, és az azt követő évektől kezdve minden évben egy újabb ágat hoz. Hány ága lesz a fának 5, 10, n év múlva?

Megjegyzés: Ez a példa természetesen nem jeleni azt, hogy bármely konkrét fafajtánál az ágak ilyen szabály szerint hajtanának.

A Fibonacci sorozat kapcsolatban van az aranymetszéssel, nevezetesen a sorozat egyre nagyobb sorszámú elemeinek hányadosa egy állandó számhoz, az aranymetszéssel kapott hosszabbik szakasznak a rövidebbikhez való arányához közelít.