Задача 34952

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

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

Условие

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

Подсказка

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

Решение

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

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

web-сайт

задача