Задача 60561

Тема:    [ Числа Фибоначчи ]

Сложность: 3+ Классы: 8,9

Условие

О том, как прыгают кузнечики. Предположим, что имеется лента, разбитая на клетки и уходящая вправо до бесконечности. На первой клетке этой ленты сидит кузнечик. Из любой клетки кузнечик может перепрыгнуть либо на одну, либо на две клетки вправо. Сколькими способами кузнечик может добраться до n-ой от начала ленты клетки?

Решение

Пусть a_n — количество способов, которыми кузнечик может добраться до n-ой клетки. Тогда a₁ = a₂ = 1. Кроме того, в n + 1-ую клетку кузнечик может попасть либо из n-ой клетки, либо перепрыгнув n-ую клетку. Поэтому a_{n + 1} = a_{n - 1} + a_n. Отсюда a_n = F_{n - 1}.

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	3
Название	Алгоритм Евклида и основная теорема арифметики
Тема	Алгебра и арифметика
параграф
Номер	4
Название	О том, как размножаются кролики
Тема	Классическая комбинаторика
задача
Номер	03.109