Задача 78286

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

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

Условие

Доказать, что любое натуральное число можно представить в виде суммы нескольких различных членов последовательности 1, 2, 3, 5, 8, 13, ..., a_n = a_{n - 1} + a_{n - 2},....

Решение

Докажем требуемое утверждение по индукции. База индукции очевидна. Последовательность {a_n} монотонно возрастает, поэтому для любого натурального числа m можно выбрать n так, что a_nm < a_n+1. По предположению индукции число m - a_n (если оно отлично от нуля) можно представить в виде суммы нескольких разных членов последовательности {a_n}. При этом m - a_n < a_{n + 1} - a_n = a_{n - 1}. Значит, в этом разложении не присутствует даже a_{n - 1}, и, тем более, не присутствует a_n.

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

олимпиада
Название	Московская математическая олимпиада
год
Номер	25
Год	1962
вариант
	1
Класс	10
Тур	1
задача
Номер	3