Чтобы вы знали: путь к счастью - это вовсе не дорога, а лестница. Лестница о тридцати ступенях. Но мало по ней просто прошагать. Для счастья нужно пройти все ступени только вперёд таким сочетанием разных шагов, как этого ещё никто не делал. А шаги получаются только трёх видов:
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. Итого 53 798 080 счастливцев.