Egy 13 lépcsőfokos lépcsőn hányféle képpen lehet felmenni, ha egyszerre csak egyet, vagy kettőt léphetünk?

Az első fokra 1 féleképpen, a következőre már 2 féleképpen, mert vagy az előzőről, vagy egyből 2-t lépsz. A 3.-ra vagy 3 db 1-es lépés vagy, 1 db 2-es lépés és 1 db 1-es lépés, ez összesen 3. A következő fokokra az előzőek függvényében juthatunk el. Vegyük észre, hogy minden lépcsőfokra az azt megelőző és az az előtti lehetőségek összegeként. Vagyis: 1,2,3,2+3=5,5+3=8 stb stb

Rekurzívan adódik a 13. Ezek a Fibonacci számok

elsőre 1, másodikra 1, utána 2,3,5,8,13,21,34,55,89,144,233

véletlenül a 14.-re nézted