Kvant Math Problem 162

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 1m56s
Source on kvant.digital

Problem

A sequence of natural numbers $$a_1\lt a_2\lt a_3\lt\ldots\lt a_n\lt\ldots\tag{A}$$ is such that every natural number either belongs to the sequence (A) or can be represented as the sum of two numbers from the sequence (A), possibly equal.

Prove that $a_n\le n^2$ for all $n=1$, 2, $\ldots$

Yu. G. Eroshkin, 9th-grade student

Exploration

Let $A={a_1<a_2<a_3<\cdots}$. The condition says that every natural number either lies in $A$ or can be written as $a_i+a_j$ for some $i,j$. Thus the set $A\cup (A+A)$ covers all positive integers.

A natural way to control the growth of $a_n$ is to compare how many numbers up to a threshold can be covered by the first $n$ elements. If we only use $a_1,\dots,a_n$, then at most $n$ numbers are covered directly, and at most $n(n+1)/2$ numbers can appear as sums $a_i+a_j$ with $i\le j\le n$. Hence the total number of integers that can be represented below a certain bound cannot exceed this quadratic quantity.

This suggests comparing the interval $[1,a_{n+1}-1]$ with the representable set from ${a_1,\dots,a_n}$, which should force a quadratic upper bound on $a_n$.

The delicate point is ensuring that every integer below $a_{n+1}$ not already in $A$ must indeed lie in $A+A$ using only the first $n$ terms, since larger terms are irrelevant.

Problem Understanding

This is a Type A problem. We are given an increasing sequence of natural numbers such that every positive integer belongs either to the sequence or is a sum of two (possibly equal) elements of it. We must prove that the growth of the sequence is at most quadratic, namely $a_n \le n^2$ for all $n$.

The key difficulty is converting a global covering condition into a quantitative bound on initial segments of the sequence.

Proof Architecture

We define the initial segment $A_n={a_1,\dots,a_n}$.

We prove that every integer $m<a_{n+1}$ that is not in $A_n$ lies in $A_n+A_n$.

We bound the number of distinct elements in $A_n+A_n$ by counting pairs $(i,j)$ with $1\le i\le j\le n$, giving at most $\frac{n(n+1)}{2}$ values.

We compare this with the number of integers in $[1,a_{n+1}-1]$ outside $A_n$, which equals $a_{n+1}-1-n$.

This yields an inequality bounding $a_{n+1}$ in terms of $n$, which implies $a_n\le n^2$.

The most delicate point is the comparison between set cardinalities and the sumset bound, ensuring no dependence on larger elements of $A$.

Solution

Let $A_n={a_1,\dots,a_n}$. Consider any integer $m$ satisfying $1\le m<a_{n+1}$. If $m\in A$, then $m\in A_n$ by definition of $a_{n+1}$. If $m\notin A$, then by the hypothesis of the problem, $m$ can be written as $m=x+y$ with $x,y\in A$. Since $m<a_{n+1}$ and $A$ is increasing, both $x$ and $y$ must be less than $a_{n+1}$, hence both belong to $A_n$. Therefore every integer $m\in[1,a_{n+1}-1]$ that is not in $A_n$ belongs to $A_n+A_n$.

The number of integers in $[1,a_{n+1}-1]$ that are not in $A_n$ equals $a_{n+1}-1-n$, since exactly $n$ numbers in this interval belong to $A_n$. Hence the set $A_n+A_n$ contains at least $a_{n+1}-1-n$ distinct elements not exceeding $a_{n+1}-1$.

Now we bound the size of $A_n+A_n$. Every element of this sumset has the form $a_i+a_j$ with $1\le i\le j\le n$. The number of such pairs is $\frac{n(n+1)}{2}$, hence the number of distinct sums does not exceed $\frac{n(n+1)}{2}$. Therefore

$a_{n+1}-1-n \le \frac{n(n+1)}{2}.$

Rearranging gives

$a_{n+1} \le n+1+\frac{n(n+1)}{2}=\frac{n^2+3n+2}{2}=\frac{(n+1)(n+2)}{2}.$

Replacing $n$ by $n-1$ yields

$a_n \le \frac{n(n+1)}{2}.$

For all $n\ge 1$, we have $\frac{n(n+1)}{2}\le n^2$, since this is equivalent to $n+1\le 2n$, which holds for all $n\ge 1$. Therefore

$a_n \le n^2.$

$\boxed{a_n \le n^2 \text{ for all } n\in\mathbb{N}.}$

Verification of Key Steps

The critical point is the claim that every integer $m<a_{n+1}$ not in $A_n$ lies in $A_n+A_n$. This follows because the hypothesis ensures $m\in A$ or $m=x+y$ with $x,y\in A$, and if $m<a_{n+1}$ then no summand can exceed $m$, hence both summands are $<a_{n+1}$ and therefore belong to $A_n$.

Another delicate point is bounding $|A_n+A_n|$. Distinctness of sums is irrelevant; an upper bound on distinct values is obtained by counting ordered pairs with $i\le j$, giving exactly $\frac{n(n+1)}{2}$ possibilities, so the sumset cannot contain more distinct elements than this count.

Finally, converting the inequality for $a_{n+1}$ into $a_n\le n^2$ is valid since the derived bound $\frac{n(n+1)}{2}$ is always at most $n^2$ for $n\ge 1$.

Alternative Approaches

A different approach uses a greedy covering argument: one studies the gaps in $A$ and shows that the number of integers not representable by $A_n$ forces frequent insertion of new elements, which constrains growth to quadratic order. Another viewpoint interprets $A$ as an additive basis of order $2$ and applies general bounds for bases of order $h$, where the extremal growth is polynomial of degree $h$. The direct counting argument above is more elementary and avoids general additive theory.