Дорога к счастью

Чтоб вы знали: путь к счастью - это вовсе не дорога, а лестница. Лестница о тридцати ступенях. Но мало по ней просто прошагать. Для счастья нужно пройти все ступени только вперёд таким сочетанием разных шагов, как этого ещё никто не делал. А шаги получаются только трёх видов:
1. Через две ступеньки;
2. Через одну ступеньку;
3. На следующую ступеньку.

Сколько людей смогут обрести счастье, пройдя этой лестницей?

Обозначим через S(n) число людей, которые могут пройти по лестнице в n ступенек.
Тогда S(1)=1 (один одинарный шаг), S(2)=2 (два одинарных, либо один двойной), S(3)=4 (одинарный+двойной, двойной+одинарный, три одинарных, один тройной).
Дальше. Свяжем последовательность S(n) рекуррентной формулой. Все последовательности шагов заканчиваются либо одинарным, либо двойным, либо тройным шагом. Тогда число разных людей, закончивших восхождение на n-ю ступеньку одинарным шагом равно S(n-1); число разных людей, закончивших восхождение на n-ю ступеньку двойным шагом равно S(n-2); число разных людей, закончивших восхождение на n-ю ступеньку тройным шагом равно S(n-3). Значит S(n)=S(n-1)+S(n-2)+S(n-3). Что-то похожее на числа Фибоначчи, только суммируются не предыдущие 2 члена, а предыдущие 3.

Решение