\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \renewcommand{\frak}{\mathfrak} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf A Note on Weakly Complete Sequences } \vskip 1cm \large Alyson Fox and Michael P. Knapp\footnote{Corresponding author.}\\ Department of Mathematics and Statistics\\ Loyola University Maryland\\ 4501 North Charles Street\\ Baltimore, MD 21210-2699\\ USA\\ \href{mailto:alfox@loyola.edu}{\tt alfox@loyola.edu}\\ \href{mailto:mpknapp@loyola.edu}{\tt mpknapp@loyola.edu}\\ \end{center} \vskip .2 in \begin{abstract} A weakly complete sequence is an increasing sequence of positive integers such 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. \end{abstract} \section{Introduction} The purpose of this article is to prove a special case of a conjecture of Paul \cite{mikepaul} about weakly complete sequences formed through the use of the greedy algorithm. Briefly, an increasing sequence of positive integers is \textit{weakly complete} if every sufficiently large integer can be written as a sum of distinct terms of the sequence. (We use the terminology of \cite{hon}. Other authors refer to such a sequence simply as \textit{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,\ldots, 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 \begin{eqnarray*} \lefteqn{5, 8, 9, 10, 11, 12, 48, 49, 51, 52, 248, 249, 251, 252,}\\ & & \qquad 1248, 1249, 1251, 1252, 6248, 6249, 6251, 6252, \ldots. \end{eqnarray*} Similarly, if we start with $a_1=3$ and $a_2=7$, then we obtain the sequence \begin{eqnarray*} \lefteqn{3, 7, 8, 9, 13, 14, 48, 49, 50, 195, 196, 197, 783, 784, 785,}\\ & & \qquad 3135, 3136, 3137, 12543, 12544, 12545, \ldots. \end{eqnarray*} 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\cdot 5^1 + \{ -2, -1, 1, 2\}$, the next four terms are $10\cdot 5^2 + \{ -2, -1, 1, 2\}$, the next four are $10\cdot 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\in 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. \begin{theorem} Suppose that a weakly complete sequence is defined as above and has initial terms $a_1=n$ and $a_2=n+d$, with $2 \leq d \leq n-8$. Then the elements of the sequence are exactly the elements in the set $I \cup J \cup \bigcup_{i=1}^{\infty} (an^i + S)$, where $I=\{ n\}$, $J = \{ s\in \mathbb{Z} : n+d \leq s \leq 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\leq j \leq n-1, j\neq d-1 \}. \] \end{theorem} Note that we can also write $J = (an^0 + S) \cup \{ an^0 + (d-1)\}$. This formula was first conjectured in \cite[Conjecture B]{mikepaul}, although there it is conjectured to hold for all $1\leq d \leq n-1$. In that paper, the $d=1$ case of this theorem was proved without the $d \leq n-8$ restriction. Additionally, the article \cite{mikepaul} gives formulas for the sequences obtained when $n=1$ and $d \geq 3$, and also when $n\geq 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 \cite{bir-weak, cas, erdos}, and \cite{hegyvari}. Surveys of this work can be found in \cite[Section 6]{erdgra} and \cite[Section 4.3]{pomsar}. Similarly, articles such as \cite{chen} and \cite{szevu} 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 \cite{andrews, guy, macmahon}). 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 \cite{mikepaul}. For convenience, we write $S_0 = J$ and for $i\geq 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 \cup S_0 \cup \cdots \cup 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 \leq m \leq 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\in \mathbb{Z} : a\leq x \leq 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\leq b,c$ and $b,c\leq d$ are \textit{contiguous} if $[a,b] \cup [c,d] = [a,d]$. Note that this occurs if and only if $c\leq 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 \leq j \leq n-1 \}$ and $S_i = \{ s_{i,j} : 0 \leq j \leq n-1, j\neq d-1 \}$. Finally, if $X$ and $Y$ are sets, then we define as usual \[ X + Y = \{ x+y : x\in X, y\in Y \}. \] \section{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. \begin{lemma} \label{lone} Suppose that $s,b,n$ are integers such that $s < s+b < s+n-1$, and let $S=[ s, s+n-1] \setminus \{s+b\}$. If $1 \leq m \leq 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\geq 2$, in which case the set $R_b(S)$ is an interval with two elements removed. \end{lemma} \begin{proof} We may assume without loss of generality that $s=0$, and do so throughout the proof. Thus we have \[ S = [0,n] \setminus \{ 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 \[ \left[ \frac{(n-2)(n-1)}{2}-b, \frac{(n-1)(n)}{2}-b \right], \] 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 \leq m \leq n-3$. The smallest element $r_{\mbox{\scriptsize small}}$ of $R_m(S)$ is obtained by summing the $m$ smallest elements of $S$, and the largest element $r_{\mbox{\scriptsize 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 + \cdots + a_m$, where $a_i \in S$ for each $i$, and $a_1 < a_2 < \cdots < 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, \ldots, a_{m-1}$ constant and increase $a_m$ until it equals $n-1$. Then we hold $a_1, \ldots, 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}, \ldots, 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 \in \left[ r_{\mbox{\scriptsize small}}, r_{\mbox{\scriptsize large}} \right]$ 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 \in R_m(S)$. However, the procedure fails to show that $x \in 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 \leq 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 \geq 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\in 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 + \cdots + (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, \ldots, 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, \ldots, a_{b-1}) = (0,1, \ldots, 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 \begin{eqnarray*} x & = & b + (b+2) + (b+3) + \cdots + (n-1)\\ & = & \frac{(n-1)n}{2} - \frac{b^2 + b + 2}{2}. \end{eqnarray*} 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) + \cdots + (n-1) = x+1. \] If we try to reduce any of $a_2, \ldots, 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, \ldots, a_m) = (b+2, \ldots, 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\geq 2$. Hence, when $n=2b+1$ and $b\geq 2$, the set $R_b(S) = R_{n-1-b}(S)$ is two elements short of being an interval. \end{proof} 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. \begin{lemma} \label{ltwo} a) Let $S$ and $T$ be sets, such that $S=[s, s^{\prime}]$, and $T=[t, t^{\prime}] \setminus \{b\}$, where $s \neq s^{\prime}$, $t \neq t^{\prime}$ and $t \leq b \leq t^{\prime}$. Then we have $S+T = \left[s+t, s^{\prime} + t^{\prime}\right]$. b) If instead we have $T=[t, t^{\prime}] \setminus \{b,c\}$, with $t \leq b,c \leq t^{\prime}$ and $c \geq b+2$, then $S+T = \left[s+t, s^{\prime} + t^{\prime}\right]$. \end{lemma} \begin{proof} a) We clearly have $S+T \subseteq \left[ s+t, s^{\prime} + t^{\prime}\right]$. If either $b=t$ or $b=t^{\prime}$, then $S$ and $T$ are both intervals, and it is clear that $S+T$ is also an interval. Suppose then that $t < b < t^{\prime}$. Consider the distinct numbers \[ \begin{array}{lll} s+t & \quad & s^{\prime}+(t+1)\\ (s+1)+t & \quad & s^{\prime}+(t+2)\\ \vdots & \quad & \vdots\\ s^{\prime}+t & \quad & s^{\prime}+t^{\prime} \end{array} \] These numbers form the interval $\left[ s+t, s^{\prime}+t^{\prime}\right]$, and all of them except $s^{\prime}+b$ are clearly elements of $S+T$. However, we have \[ s^{\prime}+b = \left( s^{\prime}-1\right) + (b+1). \] We have $s^{\prime}-1 \in S$ by hypothesis, and $b+1 \in T$ since $b < t^{\prime}$. Hence we also have $s^{\prime}+b \in S+T$, completing the proof. b) If either $b\in \{t, t^{\prime}\}$ or $c\in \{t, t^{\prime}\}$ 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^{\prime}+b$ and $s^{\prime}+c$ are elements of $S+T$. As above, we write \[ s^{\prime}+b = (s^{\prime}-1)+(b+1) \qquad\mbox{and}\qquad s^{\prime}+c = (s^{\prime}-1)+(c+1). \] Since $c\geq b+2$, the numbers $b+1$ and $c+1$ are both elements of $T$, and so the proof is complete. \end{proof} \section{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\cup S_0$. To do this, consider the sets $R_m(S_0)$ for $1\leq m \leq n$. Since we can rewrite $S_0 = (n+d)+[0,n-1]$, it is not hard to see that we have \begin{eqnarray*} R_m(S_0) & = & m(n+d) + [ 0 + \cdots + (m-1), (n-1) + \cdots + (n-m) ] \\ & = & \left[ m(n+d) + \frac{(m-1)m}{2}, m(2n+d-1) - \frac{(m-1)m}{2} \right]. \end{eqnarray*} We will now show that if $2\leq m \leq 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} \leq \left( m(2n+d-1) - \frac{(m-1)m}{2} \right) + 1. \] That is, the sets are contiguous if and only if \begin{equation} \label{quadratic} m^2 + m(1-n) + n + d - 1 \leq 0. \end{equation} Write $f(m)$ for the left-hand side of \eqref{quadratic}. If $m=2$ or $m=n-3$, then $f(m)=d+5-n$, which is negative since $d \leq n-8$. Since $f(m)$ is a quadratic in $m$ opening upwards, we immediately see that $f(m)\leq 0$ for $2\leq m \leq 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 \[ \left[ 2n+2d+1, \frac{3n^2 + n(2d-5)- 4d - 2}{2} \right]. \] 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 \[ \alpha_j = \frac{3n^2 + n(2d-5) - 4d - 2}{2} + j, \qquad 1 \leq j \leq d+1. \] To represent these, first note that if $j=1$, then we have the representation \[ \alpha_1 = n + (n+d) + \sum_{i=n+d+2}^{2n + d - 2} i. \] For the other values of $j$, note that we have \[ n + \sum_{\genfrac{}{}{0pt}{}{s \in S_0}{s \neq n+d}} = \alpha_j + (2n + d + 1 - j). \] Thus we can represent $\alpha_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\leq m \leq n-1$, we see that we have representations for every element of the interval \[ \left[ 2n+2d+1, \frac{3n^2 + n(2d-3) - 2d}{2} \right]. \] 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) = \left[ \frac{3n^2 + n(2d-3) - 2d + 2}{2}, \frac{3n^2 + n(2d-1) - 2d}{2} \right]. \] 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\cup 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\cup S_0$. One can compute that the sum of all the elements of $I \cup S_0$ is \[ n + \sum_{s\in 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 \[ \left( \frac{3n^2 + n}{2} + nd \right) - 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} \not\in 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 \cup S_0 \cup S_1 \cup \cdots \cup 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 \leq m \leq n-1$. If $1\leq m \leq d-1$, then the smallest element of $R_m(S_k)$ is \[ man^k - mb + (0 + \cdots + (m-1)), \] and if $m\geq d$, then the smallest element is \[ man^k - mb + (0 + \cdots + 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}, & \text{if $1\leq m \leq d-1$;}\\ man^k - mb + \frac{m(m+1)}{2} - d + 1, & \text{if $d \leq m \leq n-1$.} \end{cases} \] Similarly, if $c_m^{\prime}$ represents the largest element of $R_m(S_k)$, then we find that \[ c_m^{\prime} = \begin{cases} man^k - mb + mn - \frac{m(m+1)}{2}, & \text{if $1\leq m \leq n-d$;}\\ \text{\small $man^k - mb + (m+1)n - \frac{m^2 + 3m}{2} - d$,} & \text{\small if $n-d+1 \leq m \leq n-1$.} \end{cases} \] Let $C_m = [c_m, c_m^{\prime}]$. By Lemma \ref{lone}, 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 \ref{lone}, 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\geq 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 = \sum_{i=0}^{k-1} \sum_{s\in S_i} s \] and \[ (n-2)an^k - (n-2)b + \frac{(n-1)n}{2} - 2d + 2 = \sum_{i=0}^{k-1}\sum_{s\in S_i} s + \sum_{\genfrac{}{}{0pt}{}{j=0}{j\neq 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} = \sum_{i=0}^{k-1} \sum_{s\in S_i} s + \sum_{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} = \sum_{i=0}^{k-1}\sum_{s\in S_i} s + \sum_{j=d+1}^{n-1} s_{k,j}. \] Hence, for $1 \leq m \leq 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 \in 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^{\prime} ] \] 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] \subseteq R(P_{k-1})$. If we write \[ D_m = \left[ n+d, an^k - b - 1 \right] + 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\geq 3$, and the missing elements differ by $(d-2)(d+1) \geq 2$. Then Lemma 2b shows that $D_m$ is an interval.) In fact, we have $D_m = [d_m,d_m^{\prime}]$, where \[ d_m = \begin{cases} man^k - mb + \frac{(m-1)m}{2} + n + d, & \text{if $1 \leq m \leq d-1$;}\\ man^k - mb + \frac{m(m+1)}{2} + n + 1,& \text{if $d \leq m \leq n-1$} \end{cases}\ \] and \[ d_m^{\prime} = \begin{cases} {(m+1)an^k - (m+1)b + mn - \frac{m(m+1)}{2} - 1,} & \text{if $1 \leq m \leq n-d$;}\\ {(m+1)an^k - (m+1)b + (m+1)n - \frac{m^2 + 3m}{2} - d - 1,} & \text{if $n-d+1 \leq m \leq 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: \begin{itemize} \item $n+C_1$ and $D_1$ \item $D_1$ and $C_2$ \item $C_2$ and $n+C_2$ \item $n+C_2$ and $D_2$ \item $D_m$ and $D_{m+1}$ for $2 \leq m \leq n-4$ \item $D_{n-3}$ and $C_{n-2}$ \item $C_{n-2}$ and $n+C_{n-2}$ \item $n+C_{n-2}$ and $D_{n-2}.$ \end{itemize} 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 \leq (n + c_1^{\prime}) + 1$. Thus we must verify that \[ an^k - b + n + d \leq (n + an^k - b + n - 1) + 1, \] i.e., that \[ an^k - b + n + d \leq an^k - b + 2n. \] This is clearly true since $d \leq 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 \leq d \leq n-8$.) Next, we want to show that for $2\leq m \leq 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 \[ \begin{cases} m^2 + m(1-n) + n + d \leq 0, & \text{if $2 \leq m \leq \min\{ d-2, n-d \}$;} \\ m^2 + m(2-n) + 2d \leq 0, & \text{if $n-d+1 \leq m \leq d-2$;} \\ m^2 + m(2-n) + n + 2 \leq 0, & \text{if $\max\{2, d-1\} \leq m \leq \min\{ n-d, n-4\}$;} \\ m^2 + m(3-n) + d + 2 \leq 0, & \text{\small if $\max\{ d-1, n-d+1\} \leq m \leq n-4$.} \end{cases} \] 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 \leq n-8$. Suppose that $\min\{ d-2, n-d\} = d-2$. Then the condition on $m$ is that $2 \leq m \leq d-2$, which implies $d \geq 4$. In this case, $f(d-2) = d^2 - 2d + 2 - n(d-3)$. However, since $d\geq 4$, and $n \geq d + 8$, this expression is at most $-7d+26$, which is negative for $d\geq 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\geq 3$ in this case. Now, $f(n-d) = d^2 - n(d-2)$. Noting as before that $n \geq d+8$, this expression is at most $-6d + 16$, which is negative for all $d\geq 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\geq d+8$ in the theorem is required in the third case to ensure that $n\geq 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} \leq d_{n-3}^{\prime} + 1$. If $d \leq 3$, then after some algebra we find that the sets are contiguous if and only if $5-d \leq n$, which is clearly true. On the other hand, if $d \geq 4$, then algebra shows that the sets are contiguous if and only if $n \geq 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 \[ \beta_j = (n-1)an^k - (n-1)b + \frac{(n-1)n}{2} - d + l, \qquad 1 \leq l \leq n+d. \] To represent these terms, if we add \[ \sum_{i=0}^{k-1} \sum_{s\in 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 + \left[ \frac{(n-2)(n-1)}{2}, \frac{(n-1)n}{2} \right] \] except for \[ (n-1)an^k - (n-1)b + \frac{(n-1)n}{2} - d + 1. \] Similarly, if we add \[ n + \sum_{i=0}^{k-1} \sum_{s\in 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 + \left[ \frac{(n-2)(n-1)}{2} + n, \frac{(n-1)n}{2} + n \right] \] except for \[ (n-1)an^k - (n-1)b + \frac{(n-1)n}{2} - d + 1 + n. \] The two exceptions are $\beta_1$ and $\beta_{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 \begin{equation} \label{sum} \sum_{s\in P_k} s = an^{k+1} - b + d - 1 + n, \end{equation} 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 \[ \sum_{s\in P_k} s - s_{k+1, j} = d - 1 + n - j \] to remove from the sum \eqref{sum}. 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\neq 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\geq 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 \eqref{quadratic}, where we needed to have $n\geq 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