Matematyka.pl

Witam,
Mam duży problem z zadaniem o nastepującej treści: "Na ile sposobów można pokonać drogę złożoną z
n schodków, gdy za każdym razem przeskakujemy jeden stopień lub
dwa?". Bardzo prosze o naprowadzenie mnie od czego powinienem zacząć rozwiązywać ten problem, i jeżeli to mozliwe o rozwiązanie żebym mogł potem sie sprawdzić.
Z góry dziękuje

Ułóż zależność rekurencyjną.

Domyślam się że chodzi tu własnie o ułożenie zależności rekurencyjnej, ale z tym mam problem.

Przypuśćmy, że wiemy na ile sposobów można dostać się na \(\displaystyle{ k < n}\) stopni. Oznaczmy tę liczbę przez \(\displaystyle{ a_k}\). Na ile sposobów (korzystając z tych danych) możemy wejść na stopień \(\displaystyle{ n}\)-ty? Podpowiedź - możemy na niego wejść ze stopnia o numerze \(\displaystyle{ n-1}\) lub \(\displaystyle{ n-2}\).

Skoro wiemy ze na stopien \(\displaystyle{ a_1 = 1}\) i \(\displaystyle{ a_2 = 2}\) mozemy napisac wzór \(\displaystyle{ a_n = a_{n-1} + a_{n-2}}\) gdzie \(\displaystyle{ a_n}\) jest iloścą sposobów wejscia na \(\displaystyle{ n-ty}\) stopień?

Zgadza się.