Олимпиадная задача о лестнице: Сколькими способами Леша поднимется и спустится?

  а) Обозначим через а_n число способов подняться на лестницу из n ступенек, соблюдая условия задачи. Очевидно,  a₁ = 1,  a₂ = 2.   Пусть Петя запрыгивает на лестницу из  n > 2  ступенек. Если первый прыжок был на две ступеньки, то ему осталось запрыгнуть на  n – 2  ступеньки, и число способов закончить подъем равно a_n–2. Если же первый прыжок был на одну ступеньку, то число способов закончить подъем равно a_n–1. Значит,

a_n = a_n–1 + a_n–2.    Это равенство позволяет, зная a₁ и a₂, вычислять последовательно все a_n (при этом будут получаться известные числа Фибоначчи): a₃ = 3,  a₄ = 5,  a₅ = 8,  a₆ = 13,  a₇ = 21,  a₈ = 34,  a₉ = 55,  a₁₀ = 89.   б) Каждую из 9 ступенек (кроме последней) Петя может либо перепрыгнуть, либо не перепрыгнуть независимо от того, на каких из верхних ступенек он останавливался. Поэтому количество способов спуститься по лестнице равно 2⁹.