ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 34952
Темы:    [ Индукция (прочее) ]
[ Числа Фибоначчи ]
[ Системы счисления (прочее) ]
Сложность: 3+
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Докажите, что любое натуральное число можно представить в виде суммы нескольких различных членов последовательности Фибоначчи. (Последовательность Фибоначчи {an} определяется условиями a1=1, a2=2, an+2=an+1+an.)

Подсказка

Вычитайте из числа наибольшее число Фибоначчи, не превосходящее его.

Решение

Будем использовать индукцию по n. База индукции тривиальна - число 1 само является числом Фибоначчи. Далее, предположим, что все натуральные числа, меньшие некоторого числа k, можно представить в виде суммы нескольких различных членов последовательности Фибоначчи. Найдем наибольшее число Фибоначчи an, не превосходящее k. Таким образом, an не меньше k и an+1 больше k. Поскольку an+1-an=an-1, то 0<k-an<an-1. По предположению индукции число k-an представляем в виде суммы S нескольких различных членов последовательности Фибоначчи, причем из предыдущего неравенства следует, что все члены последовательности Фибоначчи, участвующие в сумме S, меньше an. Поэтому разложение числа k в сумму S+an удовлетворяет условию задачи.

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

web-сайт
задача

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .