Докажите, что любое натуральное число можно представить в виде
 суммы нескольких различных членов последовательности Фибоначчи.
 (Последовательность Фибоначчи {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
 удовлетворяет условию задачи.
			
Индукция (прочее) Числа Фибоначчи Системы счисления (прочее)