Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Source. Lemma 1, p. 2, of Wouter van Doorn, Completeness of exponentially increasing sequences, arXiv:2602.23394v1 (25 February 2026), the version named on the source card. A preprint.

Read depth. Claims checked: the statement was read clause by clause on the page images of the print; the proof was read for structure only. Nothing here is independently reviewed.

Statement

Setting (p. 1). For positive reals tt and α\alpha, St(α)=(s1,s2,…)S_t(\alpha)=(s_1,s_2,\ldots) with sn=⌊tαn⌋s_n=\lfloor t\alpha^n\rfloor, indexed from n=1n=1. For a sequence or multiset SS of positive integers, P(S)P(S) is the set of integers that are sums of distinct elements of SS; SS is complete when N∖P(S)\mathbb N\setminus P(S) is finite and entirely complete when P(S)=NP(S)=\mathbb N. Throughout, φ=(1+5)/2\varphi=(1+\sqrt5)/2.

Lemma 1 (p. 2). Suppose a positive integer m∉P(St(α))m\notin P(S_t(\alpha)) and a non-negative integer rr satisfy

s1+⋯+sr<m<sr+2,s_1+\cdots+s_r<m<s_{r+2},

and sn+sn+1≤sn+2s_n+s_{n+1}\le s_{n+2} for every n>rn>r. Then for every k≥1k\ge1,

m+sr+3+sr+5+⋯+sr+2k+1∉P(St(α)).m+s_{r+3}+s_{r+5}+\cdots+s_{r+2k+1}\notin P(S_t(\alpha)).

The paper records that Graham (1964) attributes the lemma to Folkman, and that it has found no reference for it (p. 2).

Proof pointer

Induction on kk (p. 2): the shifted integer stays strictly between the sum of all earlier terms and the term two places on, so any representation of it must use the newest odd-offset term, and removing that term would represent the previous integer.

Dependencies

None beyond the definitions.

Bears on

  • Problem 349: the tool behind Corollary 1, through which the paper proves non-completeness for α≥φ\alpha\ge\varphi; on its own the lemma gives no completeness verdict for any pair.