Задача 60581

Темы:    [ Числа Фибоначчи ] [ Треугольник Паскаля и бином Ньютона ] [ Индукция (прочее) ]

Сложность: 3+ Классы: 9,10,11 Название задачи: Числа Фибоначчи и треугольник Паскаля.

Условие

Докажите равенство:  
(Сумма, стоящая в левой части, может быть интерпретирована, как сумма элементов треугольника Паскаля, стоящих в одной диагонали.)

Подсказка

Равенство можно доказать методом математической индукции. Другое решение можно получить, если воспользоваться задачами 60576 и 60403.

Решение 1

Проверим, что данные суммы S_n удовлетворяют рекуррентному определению чисел Фибоначчи:

Решение 2

Рассмотрим последовательности длины  n – 1,  состоящие из нулей и единиц, в которых нет двух рядом стоящих единиц. Согласно задаче 60576 количество таких последовательностей равно F_n+1. С другой стороны, согласно задаче 60403 число таких последовательностей, содержащих ровно k единиц, равно      Суммируя по  k ≤ ⁿ/₂  (большего числа единиц быть не может), получаем нужное равенство.

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

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