A Note on Weakly Complete Sequences

Alyson Fox and Michael P. Knapp^{1} Department of Mathematics and Statistics Loyola University Maryland 4501 North Charles Street Baltimore, MD 21210-2699 USA

                       alfox@loyola.edu
                      mpknapp@loyola.edu

Abstract

A weakly complete sequence is an increasing sequence of positive integers with the property that every sufficiently large integer can be written as a sum of distinct terms of the sequence. In this article, we give a partial proof of a conjecture of Paul giving a formula for weakly complete sequences formed using a natural procedure.

1 Introduction

The purpose of this article is to prove a special case of a conjecture of Paul [10] about weakly complete sequences formed through the use of the greedy algorithm. Briefly, an increasing sequence of positive integers is weakly complete if every sufficiently large integer can be written as a sum of distinct terms of the sequence. (We use the terminology of [9]. Other authors refer to such a sequence simply as complete.) In this work, we are interested in sequences with two given initial terms a_{1} and a_{2}, and such that all integers greater than a_{2} are sums of terms of the sequence. A natural way to produce such a sequence is to use the greedy algorithm. That is, once the terms a_{1}, …, a_{k} are known, we define a_{k+1} to be the smallest number greater than a_{k} which can not be written as a sum of terms already in the sequence. For example, if we set a_{1} = 5 and a_{2} = 8, then we obtain the sequence

1Corresponding author.

5, 8, 9, 10, 11, 12, 48, 49, 51, 52, 248, 249, 251, 252,
1248, 1249, 1251, 1252, 6248, 6249, 6251, 6252, ….

Similarly, if we start with a_{1} = 3 and a_{2} = 7, then we obtain the sequence

3, 7, 8, 9, 13, 14, 48, 49, 50, 195, 196, 197, 783, 784, 785,
3135, 3136, 3137, 12543, 12544, 12545, ….

One can see that shortly after the initial terms, the terms of these sequences appear to organize themselves very nicely. In our first example, the four terms after 12 are 10 · 5^{1} + {−2, −1, 1, 2}, the next four terms are 10 · 5^{2} + {−2, −1, 1, 2}, the next four are 10 · 5^{3} + {−2, −1, 1, 2}, and so on. (Here, as is usual, if a is a real number and S is a set then we define a + S = {a + s : s ∈ S}. As a general program of study, we are interested in understanding the structure of sequences defined in this manner, and to know whether they always display the types of patterns indicated in the above examples.

In this article, we describe exactly the sequences produced when the initial terms satisfy a mild condition. In particular, we prove the following theorem.

Theorem 1. Suppose that a weakly complete sequence is defined as above and has initial terms a_{1} = n and a_{2} = n + d, with 2 ≤ d ≤ n − 8. Then the elements of the sequence are exactly the elements in the set I ∪ J ∪ ⋃_{i=1}^{∞}(an^{i} + S), where I = {n}, J = {s ∈ ℤ : n + d ≤ s ≤ 2n + d − 1}, and we have

a = \frac{3n^{2} + n(2d − 3) − 4d + 2}{2(n − 1)}.

To define the set S, let

b = \frac{n^{2} − n − 2d + 2}{2(n − 1)},

and then let

S = {−b + j : 0 ≤ j ≤ n − 1, j ≠ d − 1}.

Note that we can also write J = (an^{0} + S) ∪ {an^{0} + (d − 1)}.

This formula was first conjectured in [10, Conjecture B], although there it is conjectured to hold for all 1 ≤ d ≤ n − 1. In that paper, the d = 1 case of this theorem was proved without the d ≤ n − 8 restriction. Additionally, the article [10] gives formulas for the sequences obtained when n = 1 and d ≥ 3, and also when n ≥ 2 and d = n.

We note here that a fair amount of research has been done on weakly complete sequences, such as that found in [2, 3, 5], and [8]. Surveys of this work can be found in [6, Section 6] and [12, Section 4.3]. Similarly, articles such as [4] and [13] treat the related situation where it is only asked that the set of sums of elements of the sequence contain an infinite arithmetic progression. However, the focus in all of these articles is to start with some property of a sequence (usually that its counting function is large), and show that all sequences with this property must be weakly complete. This differs from our focus of starting with a method for producing weakly complete sequences and studying the structure of the sequences produced. The work closest in spirit to ours appears to be that on MacMahon’s prime numbers of measurement (see [1, 7, 11]). However, in this case, MacMahon’s construction yields only one sequence (although this can easily be generalized) and, more importantly, numbers are required to be represented as a sum of consecutive terms of the sequence.

Our strategy for proving this theorem follows that used in [10]. For convenience, we write S_{0} = J and for i ≥ 1, we write S_{i} for the set an^{i} + S. We first show that the initial terms of the sequence are given by the elements of I, S_{0}, and S_{1}. After this, we induct on i, assuming that the elements of P_{i} = I ∪ S_{0} ∪ ⋯ ∪ S_{i} are known to be the initial terms, and showing that the next terms are the elements of S_{i+1}. To do this, we essentially consider the sets of numbers which can be represented using elements of P_{i−1} and exactly m elements of S_{i} (1 ≤ m ≤ n − 1). We will show that these sets are intervals which typically either overlap or contain consecutive sets of integers (so that there are no “gaps” between them). With a little extra work, this will show that all numbers less than the smallest element of S_{i+1} can be written as sums of elements of P_{i}. After this, it will be straightforward to show that the elements of S_{i+1} cannot be written as sums of previous terms, and are hence the next terms of the sequence.

We end this introduction by giving some of the notation and terminology used in the proof of the theorem. If S is a set, then we define R(S) to be the set of sums of distinct elements of S, and R_{m}(S) to be the set of all sums of (exactly) m distinct elements of S. We typically use “integer interval” notation, so that [a, b] = {x ∈ ℤ : a ≤ x ≤ b}. For example, we will write S_{0} = J = [n + d, 2n + d − 1]. We say that two intervals [a, b] and [c, d] with a ≤ b, c and b, c ≤ d are contiguous if [a, b] ∪ [c, d] = [a, d]. Note that this occurs if and only if c ≤ b + 1. Also, it will be convenient to define the numbers s_{i,j} = an^{i} − b + j. Thus we have S_{0} = {s_{0,j} : 0 ≤ j ≤ n − 1} and S_{i} = {s_{i,j} : 0 ≤ j ≤ n − 1, j ≠ d − 1}. Finally, if X and Y are sets, then we define as usual

X + Y = {x + y : x ∈ X, y ∈ Y }.

2 Preliminary lemma

In this section, we prove two lemmas which we need in the proof of the theorem. Our first lemma yields information about the structure of the sets R_{m}(S) when S is “almost” an interval.

Lemma 2. Suppose that s, b, n are integers such that s < s + b < s + n − 1, and let S = [s, s + n − 1] \ {s + b}. If 1 ≤ m ≤ n − 1, then the set R_{m}(S) is an interval except for m = 1, b, n − 1 − b, n − 2. For these exceptional values of m, the set R_{m}(S) is an interval with exactly one element removed, unless n = 2b + 1 and b ≥ 2, in which case the set R_{b}(S) is an interval with two elements removed.

Proof. We may assume without loss of generality that s = 0, and do so throughout the proof. Thus we have

S = [0, n] \ {b}.

If m = 1, then the sumset is simply S, which is an interval with the element b deleted. If m = n−2, then we are interested in sums of all but one element of S. We may think of these as the numbers obtained by subtracting one element of S from the sum of all the elements. Thus in the same way as in the m = 1 case, we see that R_{n−2}(S) is the interval

[\frac{(n − 2)(n − 1)}{2} − b, \frac{(n − 1)(n)}{2} − b] ,

except that the element \frac{(n−1)(n)}{2} − 2b is missing. Also, the set R_{n−1}(S) is obviously an “interval” consisting of a single number, the sum of all the elements of S. Hence the lemma is true for these values of m.

Now suppose that 2 ≤ m ≤ n − 3. The smallest element r_{small} of R_{m}(S) is obtained by summing the m smallest elements of S, and the largest element r_{large} of R_{m}(S) is obtained by summing the m largest elements of S. If x is a number between these extremes, then we will try to represent it as x = a_{1} +a_{2} +⋯+a_{m}, where a_{i} ∈ S for each i, and a_{1} < a_{2} < ⋯ < a_{m}.

We begin by setting the a_{i} equal to the m smallest elements of S, and note that none of these initial values is equal to b. Then we represent successively larger numbers in the following manner. First we keep a_{1}, …, a_{m−1} constant and increase a_{m} until it equals n − 1. Then we hold a_{1}, …, a_{m−2}, a_{m} constant and increase a_{m−1} until it equals the second-largest element of S. (This is n−2 unless we have b = n−2, in which case this number is n−3.) We continue in this manner, successively increasing a_{m−2}, a_{m−3}, …, a_{1} until the values of the a_{i} are the m largest elements of S. Note that as we increase a term a_{i}, neither the initial nor final value of a_{i} is allowed to equal b, although we may have a_{i} = b between these extremes.

This procedure shows that all numbers x ∈ [r_{small}, r_{large}] are elements of R_{m}([0, n − 1]). If none of the a_{i} in the representation of x are equal to b, then we have shown that x ∈ R_{m}(S). However, the procedure fails to show that x ∈ R_{m}(S) for each value of x for which one of the a_{i} equals b. For these values, we modify our representation in one of two ways. If it happens that a_{i} = b and a_{i−1} = c ≤ b − 3, then in our representation of x we instead set a_{i−1} = c + 1 and a_{i} = b − 1. Or, if it happens that a_{i} = b and a_{i+1} = c ≥ b + 3, then we change our representation of x by setting a_{i+1} = c − 1 and a_{i} = b + 1. If either of these conditions occurs, then this modified representation shows that x ∈ R_{m}(S).

We now examine the situations in which these conditions both fail. First, note that if a_{i−1} = b − 1, then a_{i} = b must be the initial value of a_{i}, which is prohibited by our procedure. Similarly, if a_{i+1} = b + 1, then a_{i} = b must be the final value of a_{i}, which is again prohibited. Hence there are three possible situations in which our modifications fail to yield a representation of x. First, we could have a_{i−1} = b − 2 and a_{i+1} = b + 2. Second, we could have a_{i−1} = b − 2 and i = m, so that there is no a_{i+1} term. Finally, we could have a_{i+1} = b + 2 and i = 1, so that a_{i−1} does not exist.

In the first case, we have m = n − 2, which we have already handled. In the second case, we have

x = 0 + 1 + ⋯ + (b − 2) + b = \frac{b^{2} − b + 2}{2},

and x needs to be represented using exactly m = b elements of S. However, using the b smallest elements of S yields a representation of x − 1. If we attempt to increase the value of any of a_{1}, …, a_{b−1}, then all of the a_{i} with larger subscripts must also increase, making the sum of the a_{i} greater than x. Hence if we try to represent x, we must have

(a_{1}, a_{2}, …, a_{b−1}) = (0, 1, …, b − 2).

But this forces us to set a_{b} = b, which is not allowed. Hence this value of x cannot be an element of R_{b}(S).

Finally, in the last case, we have m = n − 1 − b and

x = b + (b + 2) + (b + 3) + ⋯ + (n − 1)
= \frac{(n − 1)n}{2} − \frac{b^{2} + b + 2}{2}.

We need to show that x cannot be represented using exactly n − 1 − b elements of S. If we try to use the n − 1 − b largest elements of S, we find that we have represented

(b + 1) + (b + 2) + ⋯ + (n − 1) = x + 1.

If we try to reduce any of a_{2}, …, a_{m}, then any a_{i} with a smaller subscript must also be reduced, and the sum of the a_{i} would become smaller than x. Thus, any representation of x must have

(a_{2}, …, a_{m}) = (b + 2, …, n − 1).

However, this forces us to take a_{1} = b, which is not allowed. Therefore this value of x cannot be an element of R_{n−1−b}(S).

If m is not one of the exceptional values listed in the lemma, then our modifications work, and R_{m}(S) is an interval. If m is an exceptional value and the exceptional values are distinct, then for each of these values, R_{m}(S) is exactly one element short of being an interval. Finally, we examine the situations in which the exceptional values are not distinct. We already know that R_{1}(S) and R_{n−2}(S) are exactly one element away from being an interval, and so the only case of interest is when b = n − 1 − b. In this situation, the value of x without a representation coming from m = b above is (1/2)(b^{2} − b + 2), while the exceptional value of x coming from the m = n − 1 − b case is (1/2)(3b^{2} + b − 2). These are equal if b = 1, but distinct if b ≥ 2. Hence, when n = 2b + 1 and b ≥ 2, the set R_{b}(S) = R_{n−1−b}(S) is two elements short of being an interval.

Our second lemma essentially states that if we take the sumset of an interval and a set which is almost an interval, then this sumset is an interval.

Lemma 3. a) Let S and T be sets, such that S = [s, s′], and T = [t, t′] \ {b}, where s ≠ s′, t ≠ t′ and t ≤ b ≤ t′. Then we have S + T = [s + t, s′ + t′].

b) If instead we have T = [t, t′] \ {b, c}, with t ≤ b, c ≤ t′ and c ≥ b + 2, then S + T = [s + t, s′ + t′].

Proof. a) We clearly have S + T ⊆ [s + t, s′ + t′]. If either b = t or b = t′, then S and T are both intervals, and it is clear that S + T is also an interval. Suppose then that t < b < t′. Consider the distinct numbers

\begin{matrix}s + t & s′ + (t + 1) \\ (s + 1) + t & s′ + (t + 2) \\ ⋮ & ⋮ \\ s′ + t & s′ + t′ \end{matrix}

These numbers form the interval [s + t, s′ + t′], and all of them except s′ + b are clearly elements of S + T. However, we have

s′ + b = (s′ − 1) + (b + 1).

We have s′−1 ∈ S by hypothesis, and b+1 ∈ T since b < t′. Hence we also have s′+b ∈ S+T, completing the proof.

b) If either b ∈ {t, t′} or c ∈ {t, t′} then this follows from part a) of the lemma. Otherwise, we proceed in the same way as above, and find that all numbers except s′ + b and s′ + c are elements of S + T. As above, we write

s′ + b = (s′ − 1) + (b + 1) and s′ + c = (s′ − 1) + (c + 1).

Since c ≥ b + 2, the numbers b + 1 and c + 1 are both elements of T, and so the proof is complete.

3 The proof of the theorem

In this section, the expressions S_{i}, R(S_{i}), R_{m}(S_{i}), s_{i,j}, and so on are defined as in the introduction.

By definition, the first two terms of the sequence are n and n + d. Since the smallest possible sum of elements in the sequence is 2n + d, no number from n + d + 1 to 2n + d − 1 can be represented as a sum of sequence elements. Thus these numbers must be the next terms of the sequence. Note that, along with n + d, these numbers are exactly the elements of S_{0}.

Now we begin our induction by showing that the elements of S_{1} are the next terms of the sequence. We first need to show that all of the numbers between n + d and s_{1,0} = an − b can be expressed as sums of elements of I ∪ S_{0}. To do this, consider the sets R_{m}(S_{0}) for 1 ≤ m ≤ n. Since we can rewrite S_{0} = (n + d) + [0, n − 1], it is not hard to see that we have

R_{m}(S_{0}) = m(n + d) + [0 + ⋯ + (m − 1), (n − 1) + ⋯ + (n − m)]
= [m(n + d) + \frac{(m − 1)m}{2}, m(2n + d − 1) − \frac{(m − 1)m}{2}] .

We will now show that if 2 ≤ m ≤ n − 3 then the sets R_{m}(S_{0}) and R_{m+1}(S_{0}) are contiguous. This occurs if and only if

(m + 1)(n + d) + \frac{m(m + 1)}{2} ≤ (m(2n + d − 1) − \frac{(m − 1)m}{2}) + 1.

That is, the sets are contiguous if and only if

m^{2} + m(1 − n) + n + d − 1 ≤ 0.  (1)

Write f(m) for the left-hand side of (1). If m = 2 or m = n−3, then f(m) = d+5−n, which is negative since d ≤ n−8. Since f(m) is a quadratic in m opening upwards, we immediately see that f(m) ≤ 0 for 2 ≤ m ≤ n − 3, as desired. Since these intervals are contiguous, we see that we can find representations for all numbers from the smallest element of R_{2}(S_{0}) to the largest element of R_{n−2}(S_{0}). That is, we can represent every element of the interval

[2n + 2d + 1, \frac{3n^{2} + n(2d − 5) − 4d − 2}{2}] .

Now, comparing the upper endpoint of R_{n−2}(S_{0}) and the lower endpoint of R_{n−1}(S_{0}), we see that these intervals are not contiguous, and we do not yet have representations for the numbers

α_{j} = \frac{3n^{2} + n(2d − 5) − 4d − 2}{2} + j, 1 ≤ j ≤ d + 1.

To represent these, first note that if j = 1, then we have the representation

α_{1} = n + (n + d) + ∑_{i=n+d+2}^{2n+d−2} i.

For the other values of j, note that we have

n + ∑_{{s∈S_{0} \atop s≠n+d}} = α_{j} + (2n + d + 1 − j).

Thus we can represent α_{j} if we can remove numbers summing to 2n + d + 1 − j from the sum on the left. But this is clearly possible since 2n + d + 1 − j lies in the interval [2n, 2n + d − 1], which is a subinterval of S_{0} not containing n+d. Combining these numbers with the numbers represented by R_{m}(S_{0}), 2 ≤ m ≤ n−1, we see that we have representations for every element of the interval

[2n + 2d + 1, \frac{3n^{2} + n(2d − 3) − 2d}{2}] .

Next, we can see that the interval above is contiguous with both of the intervals

n + S_{0} = [2n + d, 3n + d − 1]

and

n + R_{n−1}(S_{0}) = [\frac{3n^{2} + n(2d − 3) − 2d + 2}{2}, \frac{3n^{2} + n(2d − 1) − 2d}{2}] .

Since we have not used the term n in a representation of any element of S_{0} or R_{n−1}(S_{0}), we can represent all the numbers in these two intervals. Combining all of our intervals and noting that the upper endpoint of n + R_{n−1}(S_{0}) is s_{1,0} − 1, we see that all numbers from n + d + 1 to s_{1,0} − 1 can be represented by elements of I ∪ S_{0}.

Now we need to show that the elements of S_{1} are the next elements of the sequence. First, note that since any two elements of S_{1} differ by at most n − 1, no element of S_{1} could possibly be used in the representation of another element of S_{1}. Thus we may consider representations involving only elements of I ∪ S_{0}. One can compute that the sum of all the elements of I ∪ S_{0} is

n + ∑_{s∈S_{0}} s = \frac{3n^{2} + n}{2} + nd.

Hence we can represent an element s_{1,j} (where the numbers s_{i,j} are defined as in the introduction) if and only if we can remove from this sum numbers summing to the difference

(\frac{3n^{2} + n}{2} + nd) − s_{1,j} = n + d − 1 − j.

However, since the second-smallest element of the sequence is n + d, we can only do this if we have n + d − 1 − j = n. That is, s_{1,j} can be represented if and only if j = d − 1. Since s_{1,d−1} ∉ S_{1}, the elements of S_{1} cannot be represented by previous elements, and hence must be the next terms of the sequence.

Now we assume that the sequence begins with P_{k} = I ∪ S_{0} ∪ S_{1} ∪ ⋯ ∪ S_{k} for some k, and show that the next elements of the sequence must be the elements of S_{k+1}. First, we need to show that every integer from n + d to s_{k+1,0} − 1 can be represented by elements of P_{k}. By the definition of the sequence, we know that all of the integers up to s_{k,n−1} = an^{k} − b + n − 1 can be represented, so we only need to worry about the others.

Consider the sets R_{m}(S_{k}) for 1 ≤ m ≤ n−1. If 1 ≤ m ≤ d−1, then the smallest element of R_{m}(S_{k}) is

man^{k} − mb + (0 + ⋯ + (m − 1)),

and if m ≥ d, then the smallest element is

man^{k} − mb + (0 + ⋯ + m) − (d − 1).

Call this smallest element c_{m}, so that we have

c_{m} = \begin{cases}man^{k} − mb + \frac{(m−1)m}{2}, & if 1 ≤ m ≤ d − 1; \\ man^{k} − mb + \frac{m(m+1)}{2} − d + 1, & if d ≤ m ≤ n − 1. \end{cases}

Similarly, if c′_{m} represents the largest element of R_{m}(S_{k}), then we find that

c′_{m} = \begin{cases}man^{k} − mb + mn − \frac{m(m+1)}{2}, & if 1 ≤ m ≤ n − d; \\ man^{k} − mb + (m + 1)n − \frac{m^{2}+3m}{2} − d, & if n − d + 1 ≤ m ≤ n − 1. \end{cases}

Let C_{m} = [c_{m}, c′_{m}]. By Lemma 2, with b = d − 1, we see that R_{m}(S_{k}) = C_{m} unless m is one of the numbers 1, d − 1, n − d, or n − 2. From the proof of Lemma 2, we almost have R_{1}(S_{k}) = C_{1}, except that R_{1}(S_{k}) is missing the element an^{k} − b + d − 1. Similarly, R_{n−2}(S_{k}) is missing only the element

(n − 2)an^{k} − (n − 2)b + \frac{(n − 1)n}{2} − 2d + 2

of C_{n−2}. In the same way, R_{d−1}(S_{k}) is missing only the element

(d − 1)an^{k} − (d − 1)b + \frac{d^{2} − 3d + 4}{2}

and R_{n−d}(S_{k}) is missing only the element

(n − d)an^{k} − (n − d)b + \frac{(n − 1)n}{2} − \frac{d^{2} − d + 2}{2}.

(If n = 2d − 1 so that d − 1 = n − d, and d ≥ 3, then this should be interpreted as meaning that the set R_{d−1}(S_{k}) = R_{n−d}(S_{k}) is missing two elements.)

We now show that the numbers which keep the sets R_{m}(S_{k}) from being intervals do have representations. One can verify that we have

an^{k} − b + d − 1 = ∑_{i=0}^{k−1} ∑_{s∈S_{i}} s

and

(n − 2)an^{k} − (n − 2)b + \frac{(n − 1)n}{2} − 2d + 2 = ∑_{i=0}^{k−1} ∑_{s∈S_{i}} s + ∑_{{j=0 \atop j≠d−2,d−1,d}}^{n−1} s_{k,j}.

(Again, the numbers s_{i,j} are defined as in the introduction.) To see that the other two numbers have representations, we have

(d − 1)an^{k} − (d − 1)b + \frac{d^{2} − 3d + 4}{2} = ∑_{i=0}^{k−1} ∑_{s∈S_{i}} s + ∑_{j=0}^{d−3} s_{k,j}

and

(n − d)an^{k} − (n − d)b + \frac{(n − 1)n}{2} − \frac{d^{2} − d + 2}{2} = ∑_{i=0}^{k−1} ∑_{s∈S_{i}} s + ∑_{j=d+1}^{n−1} s_{k,j}.

Hence, for 1 ≤ m ≤ n − 1, all elements in the set C_{m} are represented by elements of P_{k}. Note that none of these representations use the term n of the sequence.

Now, if x ∈ C_{m}, then by adding n to the representation of x, we obtain a representation of n + x. Hence all numbers in the intervals

n + C_{m} = [n + c_{m}, n + c′_{m}]

can be represented by elements of P_{k}.

Next, the definition of the sequence tells us that we have [n + d, an^{k} − b − 1] ⊆ R(P_{k−1}). If we write

D_{m} = [n + d, an^{k} − b − 1] + R_{m}(S_{k}),

then D_{m} is an interval for each value of m. (If R_{m}(S_{k}) is an interval, then this is clear. If it is one element short of being an interval, then this is true by Lemma 2a. If R_{m}(S_{k}) is missing two elements, then we have n = 2d − 1, with d ≥ 3, and the missing elements differ by (d − 2)(d + 1) ≥ 2. Then Lemma 2b shows that D_{m} is an interval.) In fact, we have D_{m} = [d_{m}, d′_{m}], where

d_{m} = \begin{cases}man^{k} − mb + \frac{(m−1)m}{2} + n + d, & if 1 ≤ m ≤ d − 1; \\ man^{k} − mb + \frac{m(m+1)}{2} + n + 1, & if d ≤ m ≤ n − 1 \end{cases}

and

d′_{m} = \begin{cases}(m + 1)an^{k} − (m + 1)b + mn − \frac{m(m+1)}{2} − 1, & if 1 ≤ m ≤ n − d; \\ (m + 1)an^{k} − (m + 1)b + (m + 1)n − \frac{m^{2}+3m}{2} − d − 1, & if n − d + 1 ≤ m ≤ n − 1. \end{cases}

It is clear that every element of D_{m} is represented by elements of P_{k}.

Now, recalling that all integers up to an^{k} − b + n − 1 can be represented, we prove that every number from an^{k} − b + n to s_{k+1,0} − 1 can be represented by elements of P_{k}. Note that an^{k} − b + n is the smallest element of n + C_{1} and that s_{k+1,0} − 1 is the largest element of D_{n−1}. In order to show that all these numbers have representations, we prove that the following pairs of sets are contiguous:

• n + C_{1} and D_{1}

• D_{1} and C_{2}

• C_{2} and n + C_{2}

• n + C_{2} and D_{2} • D_{m} and D_{m+1} for 2 ≤ m ≤ n − 4

• D_{n−3} and C_{n−2}

• C_{n−2} and n + C_{n−2}

• n + C_{n−2} and D_{n−2}.

It will turn out that the sets D_{n−2} and D_{n−1} are not contiguous, but we will be able to show that the numbers separating these sets can be represented.

The sets n + C_{1} and D_{1} are contiguous if and only if we have d_{1} ≤ (n + c′_{1}) + 1. Thus we must verify that

an^{k} − b + n + d ≤ (n + an^{k} − b + n − 1) + 1,

i.e., that

an^{k} − b + n + d ≤ an^{k} − b + 2n.

This is clearly true since d ≤ n − 1. Similarly, one can easily show that the sets D_{1} and C_{2} are contiguous, as are the pair C_{2} and n + C_{2} and the pair n + C_{2} and D_{2}. (For these pairs, one must consider separately the cases d = 2 and d > 2, and use the fact that 2 ≤ d ≤ n−8.)

Next, we want to show that for 2 ≤ m ≤ n−4, the intervals D_{m} and D_{m+1} are contiguous. The condition for this to occur depends on the value of m, but we can see that these sets are contiguous if and only if

m^{2} + m(1 − n) + n + d ≤ 0, if 2 ≤ m ≤ min{d − 2, n − d};
m^{2} + m(2 − n) + 2d ≤ 0,  if n − d + 1 ≤ m ≤ d − 2;
m^{2} + m(2 − n) + n + 2 ≤ 0, if max{2, d − 1} ≤ m ≤ min{n − d, n − 4};
m^{2} + m(3 − n) + d + 2 ≤ 0, if max{d − 1, n − d + 1} ≤ m ≤ n − 4.

To show that the sets are contiguous in the first case, write f(m) = m^{2} + m(1 − n) + n + d. We will show that f is negative at both endpoints. Since f is a quadratic (in m) opening upwards, this will imply that f is negative between the endpoints as well. First, we note that f(2) = 6 − n + d, which is negative due to our assumption that d ≤ n − 8.

Suppose that min{d − 2, n − d} = d − 2. Then the condition on m is that 2 ≤ m ≤ d − 2, which implies d ≥ 4. In this case, f(d − 2) = d^{2} − 2d + 2 − n(d − 3). However, since d ≥ 4, and n ≥ d + 8, this expression is at most −7d + 26, which is negative for d ≥ 4. Suppose on the other hand that min{d − 2, n − d} = n − d. If we had d = 2, then d − 2 = 0 would be the minimum. Thus we must have d ≥ 3 in this case. Now, f(n − d) = d^{2} − n(d − 2). Noting as before that n ≥ d + 8, this expression is at most −6d + 16, which is negative for all d ≥ 3. Hence f is negative at the right endpoint. As noted above, since f is negative at both endpoints, it must be negative at all points in between as well. This completes the proof that D_{m} and D_{m+1} are contiguous in the first case. We will not give the proof that the sets are contiguous in the other three cases, but the arguments in those cases are similar to this one. We note that the condition n ≥ d + 8 in the theorem is required in the third case to ensure that n ≥ 10 when d = 2 and m is either 2 or n − 4.

For the sets D_{n−3} and C_{n−2}, we must again break into cases based on the value of d, and show that c_{n−2} ≤ d′_{n−3} + 1. If d ≤ 3, then after some algebra we find that the sets are contiguous if and only if 5 − d ≤ n, which is clearly true. On the other hand, if d ≥ 4, then algebra shows that the sets are contiguous if and only if n ≥ 2, which is also true. A similar argument shows that the sets C_{n−2} and n + C_{n−2} are contiguous, and also the sets n + C_{n−2} and D_{n−2}.

Remembering that we have representations for all the numbers in the set D_{n−1}, we see that we have represented all of the numbers we need except for the ones between D_{n−2} and D_{n−1}. These are (regardless of the value of d) exactly the numbers

β_{j} = (n − 1)an^{k} − (n − 1)b + \frac{(n − 1)n}{2} − d + l, 1 ≤ l ≤ n + d.

To represent these terms, if we add

∑_{i=0}^{k−1} ∑_{s∈S_{i}} s = an^{k} − b + d − 1

to each of the elements of R_{n−2}(S_{k}), we find representations for all numbers in the interval

(n − 1)an^{k} − (n − 1)b + [\frac{(n − 2)(n − 1)}{2}, \frac{(n − 1)n}{2}]

except for

(n − 1)an^{k} − (n − 1)b + \frac{(n − 1)n}{2} − d + 1.

Similarly, if we add

n + ∑_{i=0}^{k−1} ∑_{s∈S_{i}} s = an^{k} − b + d − 1 + n

to each of the elements of R_{n−2}(S_{k}), then we find representations of all numbers in the interval

(n − 1)an^{k} − (n − 1)b + [\frac{(n − 2)(n − 1)}{2} + n, \frac{(n − 1)n}{2} + n]

except for

(n − 1)an^{k} − (n − 1)b + \frac{(n − 1)n}{2} − d + 1 + n.

The two exceptions are β_{1} and β_{n+1}, which are exactly the numbers represented by the “intervals” C_{n−1} and n + C_{n−1}. Hence they also have representations. Note that the above representations include all of the numbers that we had been missing. Thus we see that every number less than the smallest element of S_{k+1} can be represented by the elements of P_{k}.

Now we need to show that the elements of S_{k+1} are the next elements in the sequence. As before, since any two elements of S differ by at most n − 1, no element of S_{k+1} could be used in a hypothetical representation of another element of S_{k+1}. Now, since we have

∑_{s∈P_{k}} s = an^{k+1} − b + d − 1 + n,  (2)

we can represent the number s_{k+1,j} = an^{k+1} −b+j if and only if we can find a representation of the difference

∑_{s∈P_{k}} s − s_{k+1,j} = d − 1 + n − j

to remove from the sum (2). However, since this difference is smaller than n + d, it is clear that it can be represented if and only if j = d − 1. However, this is exactly the term which is excluded from the set S_{k+1}. Hence we see that the numbers s_{k+1,j} with j ≠ d − 1 cannot be represented by previous terms of the sequence, while the number s_{k+1,d−1} can be represented. Hence the elements of S_{k+1} must be the next terms of the sequence. This completes the induction, and hence also the proof of the theorem.

We close this section with a few remarks on the condition n ≥ d + 8. We believe that the theorem holds whenever n > d, and that this should be provable with a more refined analysis. We first use a hypothesis of this type immediately after equation (1), where we needed to have n ≥ d+5 to show that the sets R_{2}(S_{0}) and R_{3}(S_{0}) (and also the pair R_{n−3}(S_{0}) and R_{n−2}(S_{0})) are contiguous. If n < d + 5, then there will be gaps between these intervals, and we would need to find explicit representations for the numbers in these gaps.

Already needing to have n ≥ d + 5, at this point we simply looked for a condition of the form n ≥ d + k, with k a constant, which would guarantee that all of the other necessary pairs of intervals would be contiguous. Some condition is needed in the case of C_{2} and n+C_{2}, of n + C_{2} and D_{2}, and of D_{m} and D_{m+1}. Moreover, to show that D_{2} and D_{3} are contiguous when d = 2, we needed to have n ≥ 10, which led to the n ≥ d + 8 condition.

However, one usually needs significantly less than this. For example, one can show that the intervals C_{2} and n + C_{2} are contiguous unless we have n = 3 and d = 2, and the same is true for n + C_{2} and D_{2}. It may even be that there are a finite number of triples (n, d, m) for which D_{m} and D_{m+1} are not contiguous, and that these triples could all be treated individually.

4 Acknowledgments

The majority of this research was conducted while the first author was a participant in the Hauber Summer Research Program at Loyola College (now Loyola University Maryland) during the summer of 2009 under the direction of the second author, and this article was partially written while the second author was enjoying the hospitality of the Universidade de Brasília while on sabbatical leave. We would like to thank both the Hauber program and the Universidade de Brasília for their generous support.

References

[1] G. Andrews, Mac Mahon’s prime numbers of measurement, Amer. Math. Monthly 82 (1975), 922–923.

[2] B. J. Birch, Note on a problem of Erdős, Proc. Cambridge Philos. Soc. 55 (1959), 370–373.

[3] J. W. S. Cassels, On the representation of integers as the sums of distinct summands taken from a fixed set, Acta Sci. Math. Szeged 21 (1960), 111–124.

[4] Y.-G. Chen, On subset sums of a fixed set, Acta Arith. 106 (2003), 207–211.

[5] P. Erdős, On the representation of large integers as sums of distinct summands taken from a fixed set, Acta Arith. 7 (1961/1962), 345–354.

[6] P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory, Université de Genève L’Enseignement Mathématique, 1980.

[7] R. K. Guy, Unsolved Problems in Number Theory, Springer-Verlag, 1994.

[8] N. Hegyvári, On the completeness of an exponential type sequence, Acta Math. Hungar. 86 (2000), 127–135.

[9] R. Honsberger, Mathematical Gems III, Mathematical Association of America, 1985.

[10] M. Knapp and M. Paul, On weakly complete sequences formed by the greedy algorithm, Integers 12 (2012), A4, 17pp.

[11] P. A. MacMahon, The prime numbers of measurement on a scale, Proc. Cambridge Phil. Soc. 21 (1923), 651–654.

[12] C. Pomerance and A. Sárközy, Combinatorial number theory, in Handbook of Combinatorics, Vol. 1, 2, Elsevier, 1995, pp. 967–1018.

[13] E. Szemerédi and V. Vu, Long arithmetic progressions in sumsets: thresholds and bounds, J. Amer. Math. Soc. 19 (2006), 119–169.

2010 Mathematics Subject Classification: Primary 11B37. Keywords: weakly complete sequence.

Received September 15 2011; revised version received February 17 2012; May 28 2013. Published in Journal of Integer Sequences, June 6 2013.

Return to Journal of Integer Sequences home page.