Задача
Докажите равенство: 
(Сумма, стоящая в левой части, может быть интерпретирована, как сумма элементов треугольника Паскаля, стоящих в одной диагонали.)
Решение
Решение 1:Проверим, что данные суммы Sn удовлетворяют рекуррентному определению чисел Фибоначчи: 
Решение 2:Рассмотрим последовательности длины n – 1, состоящие из нулей и единиц, в которых нет двух рядом стоящих единиц. Согласно задаче 160576 количество таких последовательностей равно Fn+1. С другой стороны, согласно задаче 160403 число таких последовательностей, содержащих ровно k единиц, равно 
Суммируя по k ≤ n/2 (большего числа единиц быть не может), получаем нужное равенство.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет