Задача 60576

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

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

Условие

Рассмотрим множество последовательностей длины n, состоящих из 0 и 1, в которых не бывает двух 1 стоящих рядом. Докажите, что количество таких последовательностей равно F_{n + 2}. Найдите взаимно-однозначное соответствие между такими последовательностями и маршрутами кузнечика из задачи 3.109.

Подсказка

Найдите рекуррентную формулу для числа таких последовательностей. Можно также воспользоваться результатом задачи 3.109. Для этого нужно каждую единицу интерпретировать как прыжок кузнечика через клетку.

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

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