|
|
 |
Условие
Последовательность натуральных чисел a1 < a2 < a3 < ... < an < ... такова, что каждое натуральное число либо входит в последовательность, либо представимо в виде суммы двух членов последовательности, быть может, одинаковых. Докажите, что an ≤ n² для любого n = 1, 2, 3, ...
Решение
Рассмотрим первые n – 1 членов последовательности a1, ..., an–1 (1)
и все натуральные числа, которые можно представить в виде суммы двух из
этих чисел: a1 + a1, a1 + a2, ..., an + an. (2)
Общее количество чисел в (1) и (2) не превышает n – 1 + ½ n(n – 1) < n².
Таким образом, найдутся натуральные числа от 1 до n², которые не содержатся среди чисел (1) и (2). Поэтому an ≤ n².
Замечания
Мы фактически доказали, что an ≤ ½ n(n + 1).
Возможность более точной оценки см. в решениях Задачника "Кванта".
