Если неправильно - поправьте
Всего N ступенек и 3 способа подняться с каждой из них на следующую: 3^n вариантов.
Но при поднятии через одну или две ступеньки мы теряем соответственно 1 или 2 варианта. Так как все способы распределены равномерно, то:
(3^n) - (n/3)*2 - (n/3)*1.
Насчет равномерности я соврал
, потому что есть еще и конец лестницы, в котором, начиная с какого-то момента, не получится перешагнуть через 1 или 2 ступеньки:
(3^n) - (n/3)*2 - (n/3)*1 - 2 - 1.
Вроде так, или в конце рабочего дня я уже не соображаю