Kvant Math Problem 710

Verified: no
Verdicts: FAIL + FAIL
Solve time: 31m15s
Source on kvant.digital

Problem

Does there exist a sequence of distinct positive integers $a_1$, $a_2$, $a_3$, $\ldots$, none of whose terms is equal to the sum of several others, such that (for all $n=1$, 2, $\ldots$)

1. $a_n \le 2 (\sqrt{3})^n$;
2. $a_n \le 10 \cdot (1{,}5)^n$;
3. $a_n \le n^{10}$;
4. $a_n \le 1000 \cdot n^{7/2}$;
5. $a_n \le 1000 \cdot n^{3/2}$?

S. V. Konyagin

Step 1: Reformulation of the condition

The requirement that no term is equal to the sum of several others is ensured by a stronger property: for every $n$, if

$a_n > \sum_{k<n} a_k,$

then no $a_n$ can equal a sum of earlier distinct terms, since every such sum is at most the total sum of all earlier terms. A sequence satisfying this inequality is usually called superincreasing.

The task therefore splits into constructing a superincreasing sequence under the given upper bounds, or proving that such a sequence cannot exist.

Step 2: Cases (1) and (2)

For the exponential bounds, a construction is possible.

Let $r_1 = \sqrt{3}$ and $r_2 = 1.5$. Fix a constant $c>0$ and define

$a_n = \left\lfloor \frac{c,r^n}{n^3} \right\rfloor,$

where $r$ is either $r_1$ or $r_2$ depending on the case.

The sequence is strictly increasing for large $n$ since the factor $r^n/n^3$ is increasing. The upper bounds in (1) and (2) are satisfied by construction for suitable $c$.

To verify the additive condition, estimate the sum of previous terms:

$\sum_{k<n} a_k \le \sum_{k<n} \frac{c,r^k}{k^3} \le c,r^{n-1} \sum_{j\ge 0} \frac{1}{r^j} \le C,\frac{r^{n-1}}{(n-1)^3}$

for a constant $C$ depending only on $r$. Then

$\frac{a_n}{\sum_{k<n} a_k} \ge \frac{c,r^n/n^3}{C,r^{n-1}/(n-1)^3} = \frac{c}{C},r\left(\frac{n-1}{n}\right)^3,$

which exceeds $1$ for all sufficiently large $n$ after fixing $c$. Thus for large $n$,

$a_n > \sum_{k<n} a_k.$

Finite initial adjustments preserve the property, so such sequences exist for (1) and (2).

Step 3: Case (3)

Assume a sequence satisfies $a_n \le n^{10}$. Then

$\sum_{k<n} a_k \le \sum_{k<n} k^{10} \le C n^{11}$

for some constant $C$.

If infinitely many indices satisfy $a_n > \sum_{k<n} a_k$, then in particular

$a_n > C n^{11}$

for large $n$, contradicting $a_n \le n^{10}$.

Therefore no superincreasing sequence can satisfy (3), hence no sequence with the required additive property exists.

Step 4: Case (4)

Assume $a_n \le 1000,n^{7/2}$. Then

$\sum_{k<n} a_k \le C n^{9/2}$

for some constant $C$.

The same argument as in the previous case shows that any term dominating the sum of all previous terms would need growth at least on the order of $n^{9/2}$, but repeated comparison forces eventual violation of the bound $1000,n^{7/2}$. Thus no such sequence can satisfy both the growth condition and the additive restriction.

Step 5: Case (5)

Assume $a_n \le 1000,n^{3/2}$. Then

$\sum_{k<n} a_k \le C n^{5/2}.$

Again, any term exceeding the sum of all previous terms must eventually dominate $n^{5/2}$, which is incompatible with the bound $n^{3/2}$. Hence no such sequence exists.

Step 6: Final conclusion

Sequences satisfying the required additive restriction exist in the exponential cases (1) and (2) via a rapidly growing construction that dominates the sum of all previous terms while staying below the prescribed exponential bounds.

For the polynomial cases (3), (4), and (5), the cumulative growth of partial sums exceeds any allowed term growth, which prevents the existence of a sequence in which each term exceeds the sum of earlier ones, and therefore prevents the required additive property.

The answer is that such sequences exist for (1) and (2), and do not exist for (3), (4), and (5).