На земле перед лестницей стоит Петя, который собирается подняться на десятую ступеньку. Петя или шагает на следующую ступеньку или прыгает через одну ступеньку. Сколькими способами Петя может добраться до десятой ступеньки?

Предыдущий
вопрос Следующий
вопрос

Пусть f(n) обозначает количество способов, которыми Петя может добраться до n-ой ступеньки. Тогда для n >= 3 f(n) = f(n-1) + f(n-2) (поскольку Петя может либо шагнуть с предпоследней ступеньки на последнюю, либо прыгнуть с антипоследней на последнюю).

Для n = 1: f(1) = 1 (Петя может подойти и шагнуть на первую ступеньку)
Для n = 2: f(2) = 2 (Петя может либо подойти и шагнуть на вторую ступеньку, либо прыгнуть с первой на вторую)

Продолжая построение рекурсивной последовательности f(n), получим:
f(1) = 1
f(2) = 2
f(3) = f(2) + f(1) = 3
f(4) = f(3) + f(2) = 5
f(5) = f(4) + f(3) = 8
...
f(10) = f(9) + f(8) = 55

Итак, Петя может добраться до десятой ступеньки 55 способами.