Задача
№ 13179
Расстановки, размещения, раскраски, маршруты
Ур. 4
Олимпиада МЦНМО по теории вероятностей и статистике, 6–11 классы, пригласительный тур 2019/20 уч. г., вариант 2, задача 7
Из одинаковых квадратов составляется фигура: левый столбик состоит из одного-единственного квадрата, а в каждом следующем столбике на один или на два квадрата больше, чем в предыдущем. В самом правом столбике ровно $n$ квадратов. Докажите, что количество различных фигур, которые можно построить таким способом, равно $n$-му числу Фибоначчи. На рисунке показана одна из таких возможных фигур высотой 5 квадратов.
Два первых числа Фибоначчи равны единице: $f_1=1$, $f_2=1$, а далее каждое число равно сумме двух предыдущих: $f_{n+1}=f_n+f_{n-1}$.
Два первых числа Фибоначчи равны единице: $f_1=1$, $f_2=1$, а далее каждое число равно сумме двух предыдущих: $f_{n+1}=f_n+f_{n-1}$.
Ответ:
Решение: