Ха - я сперва целый лист исписал "первым" способом :) Но не помня как правильно пользоваться "цэ-от-..." получился такой непредставительный кошмар со скобками - что пришлось выкручиваться :)
Кстати, да - К2 совершенно прав, это таки Фибоначчи. Действительно, все способы преодолеть N ступенек можно разделить на две группы - сперва шагнуть на одну ступеньку и после всеми способами преодолеть N-1, или сперва шагнуть через одну ступеньку и после всеми способами преодолеть оставшиеся N-2. Очевидно, что эти две группы не пересекаются, ибо заведомо отличаются первым шагом, и составляют в сумме все способы преодолеть N ступенек. Что приводит нас к F(N)=F(N-1)+F(N-2) - собственно, определению Фибоначчи. 8)))
И забавный побочный эффект мы получаем в виде разложения F(N+1)=C(N,0)+C(N-1,1)+...+C(N-M,M) - поскольку это два разных представления одного и того же количества. 8)
Что-то не складывается красивая формула, но может просто я торможу... По сути, положим М = целая часть от N/2 (сразу заметим, что N-M >= M, соответственно). Тогда искомое количество способов равно сумме C(N,0)+C(N-1,1)+C(N-2,2)+...+C(N-M,M) . Где С() - стандартное "це-из-эн-по-ка", которое количество комбинаций.