Fibonacci sorozat

Bizonyítsuk be, hogy tetszőleges természetes n számra a következő kifejezés értéke egész szám:

Első pillantra ez egy meglepő állítás.

Az n = 0, 1 esetben az eredmény 0 és 1, az n = 2 esetben pedig egy rövid számolás után megkapjuk az eredményt, ami most is 1.
Az n = 3, 4, 5, 6, 7 … esetekben egyre bonyolultabb számítási feladat elé nézünk, de ha nem számoljuk el magunkat, akkor a következő eredményeket kapjuk: 2, 3, 5, 8, …

Nos, ezek a számok ismerősek lehetnek. Ezek a Fibonacci sorozat elemeire emlékeztetnek. Bármelyik szám az előző kettő összegeként áll elő:

Azt kellene megmutatni, hogy:

és akkor teljes indukcióval igazolnánk a feladat állítását. Hozzuk közös nevezőre a törteket:

Ás éppen ezt akartuk bizonyítani.

Tehát a fenti F szám a Fibonacci sorozat n-edik elemének explicit alakja. Másképpen Binet formulának is szokás nevezni.