Задача 109043

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

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

Условие

Дан ряд чисел 1,1,2,3,5,8,13,21,34,..., каждое из которых, начиная с третьего, равно сумме двух предыдущих. Доказать, что каждое натуральное число n>2 равно сумме нескольких различных чисел указанного ряда.

Решение

1-й способ. Проведём доказательство методом математической индукции. Число 3 можно представить как 1+2. Предположим, что число N можно представить как сумму членов данной последовательности. Докажем, что это можно сделать и для N+1 . Если в сумме, представляющей число N , нет слагаемого 1, то, прибавив к ней единицу, получим представление для N+1 , и задача будет решена. Если в этой сумме слагаемое 1 есть, но нет слагаемого 2, то, заменив единицу на 2, получим необходимое представление для N+1 . Если в сумме есть слагаемые 1 и 2, но нет слагаемого 3, то можем слагаемое 2 заменить слагаемым 3 или слагаемое 1 и 2 заменить слагаемым 3 и добавить слагаемое 1 (это одно и то же). Вообще, если в сумме, представляющей число N , содержатся в качестве слагаемых все члены нашей последовательности от 1 до a_k , а a_k+1 отсутствует, то мы a_k+a_k-1 представим как a_k+1 ; a_k-3+a_k-2 представим как a_k-1 и т. д. В итоге получим, представление для N , где либо отсутствует единица, либо отсутствует двойка. Оба этих случая были нами отдельно рассмотрены. Таким образом, если число N можно представить в виде суммы нескольких различных членов данной последовательности, то и число N+1 можно представить в таком виде. Поэтому на основании принципа математической индукции предложение справедливо для всех натуральных чисел. 2-й способ. Если натуральное число является одним из членов данной последовательности, то его можно представить как сумму двух предыдущих членов этой последовательности (если оно не 1, которая составит исключение из этого правила). Предположим, что число N не входит в данную последовательность. Тогда оно заключено между какой-то парой соседних членов последовательности a_k и a_k+1 . Выделим в нашем числе слагаемое a_k : N=a_k+x , причём x<a_k . Если x равно некоторому члену последовательности, то задача решена. Если x не равно ни одному из членов последовательности, то оно заключено между двумя меньшими членами этой последовательности: a_p и a_p+1 . Выделим из него слагаемое a_p : x=a_p+y . Тогда N=a_k+a_p+y , где y<a_p, a_p<a_k . Аналогично продолжим поступать и далее. Поскольку слагаемые x,y,... уменьшаются, процесс должен быть конечен, и мы разложим данное натуральное число в сумму нескольких различных членов данной последовательности.

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

олимпиада
Название	Белорусские республиканские математические олимпиады
олимпиада
Номер	17
Название	17-я Белорусская республиканская математическая олимпиада
Год	1967
Задача
Название	Задача 9.5