Van egy kutyám, akinek a jutalom csontját a 6. lépcsőfokra helyeztem el. Vagy egyesével vagy kettesével tud felmenni érte. Hány különböző módon jut fel a 6. lépcsőfokra? Magyarázattal!

Lépcsőfokonként érdemes lebontani a feladatot.

1. lépcső: Ide csak 1-féleképpen juthatunk el.

2. lépcső: Ide 2-féleképpen juthatunk, hiszen vagy rögtön ugrik a kutya egy nagyot, vagy a másik lehetőség szerint egyesével fellépdel.

A 3. lépcső esetén a következő a gondolatmenet: ha először lép a kutya 2-t, akkor onnan már csak 1 lépcsőfok hiányzik, ha viszont először csak 1-et lép, akkor még két lépcső hiányzik. Összesen tehát 1+2=3-féleképpen juthatunk fel a 3.-ra.

A 4. lépcsőnél már azt veheted észre, hogy ha először 1-et lépsz, akkor utána még marad 3 lépcső (amit már kiszámoltunk az előző bekezdésben), ha viszont rögtön kettőt lépünk, akkor két lépcső marad (ami a kettővel ezelőtti bekezdés), vagyis add össze az előző két eredményedet: 2+3=5-féleképpen lehet feljutni a 4.-re.

Az 5. lépcsőnél is az előző két eset összege lesz a megoldás, vagyis 3+5= 8.

És végül a hatodik lépcsőnél is csak az előző két lépcsőnél számoltakat kell összeadni, vagyis 5+8 = 13.

A 6. lépcsőfokra tehát 13-féleképpen lehet feljutni.

Akárhányadik lépcsőfokot ki tudnánk számolni, csak mindig az előző két lépcsőfoknál tapasztalt lehetőségeket kell összeadni. Ez a feladat a Fibonacci-sorozatra vezet bennünket.