ЗАДАЧИ
problems.ru |
О проекте
|
Об авторах
|
Справочник
Каталог по темам | по источникам | |
|
Задача 34952
УсловиеДокажите, что любое натуральное число можно представить в виде
суммы нескольких различных членов последовательности Фибоначчи.
(Последовательность Фибоначчи {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 удовлетворяет условию задачи. Источники и прецеденты использования
|
© 2004-...
МЦНМО
(о копирайте)
|
Пишите нам
|
![]() |
Проект осуществляется при поддержке