# Aternating sum of an increasing sequence of positive integers

Suppose $$A = (a_n) = (a_1, a_2, a_3, . . .)$$ is an positive, increasing sequence of integers.

Define an $$A$$- expressible number $$c$$ if $$c$$ is the alternating sum of a finite subsequence of $$A.$$ To form such a sum, choose a finite subset of the sequence $$A,$$ list those numbers in increasing order (no repetitions allowed), and combine them with alternating plus and minus signs. We allow the trivial case of one-element subsequences, so that each an is $$A-$$expressible.

Definition. Sequence $$A = (a_n)$$ is an “alt-basis” if every positive integer is uniquely $$A-$$ expressible. That is, for every integer $$m > 0,$$ there is exactly one way to express $$m$$ as an alternating sum of a finite subsequence of $$A.$$

Examples. Sequence $$B = (2^{n−1}) = (1, 2, 4, 8, 16, . . .)$$ is not an alt-basis because some numbers are B-expressible in more than one way. For instance $$3 = −1 + 4 = 1 − 2 + 4.$$

Sequence $$C = (3^{n−1}) = (1, 3, 9, 27, 81, . . .)$$ is not an alt-basis because some numbers (like 4 and 5) are not C-expressible.

An example of an alt-basis is $$\{2^n-1\}=\{1,3,7,15,31,\ldots\}$$

Is there a fairly simple test to determine whether a given sequence is an alt basis?

I have attempted to solve this from a limited knowledge in sequences and have found out various kinds of sequences do not work but fail to see what it is that could make it work.

• Seems slightly (at least) related to this: encyclopediaofmath.org/index.php/Additive_basis But I think you know already about additive bases. – user757601 Mar 25 at 0:37
• See math.stackexchange.com/questions/3579462. (Not an exact duplicate because it doesn't ask for a general test to determine whether a sequence is an alt-basis.) What is the source of this question? – joriki Mar 25 at 6:47
• Do you know of any alt-bases that are not of the form $\{b_1,b_2,\dots,b_k,a_{k+1},a_{k+2},\dots\}$ where $A=\{a_1,a_2,\dots\}=\{2^n-1\}$ and $\{b_1,\dots,b_k\}$ is some finite increasing set of integers? – Vepir Mar 25 at 21:54
• For example I believe that $\{5\cdot2^{n - 2} + (-1)^{n + 1} 2^{n - 2} - 1\}$ is an alt-basis. – Vepir Mar 25 at 22:50

I can’t answer the question, but I can at least give you a systematic large family of alt-bases.

If $$A$$ is a finite set of positive integers, let $$S(A)$$ be the set of $$A$$-expressible integers, and let $$S^+(A)$$ be the set of $$A$$-expressible positive integers. Then

$$S(A)=S^+(A)\cup\{-a:a\in S^+(A)\},$$

and if $$b>\max A$$, then

$$S^+\left(A\cup\{b\}\right)=S^+(A)\cup\{b-s:s\in S^+(A)\}\cup\{b\}.$$

Thus, if $$|A|=n$$, the maximum number of $$A$$-expressible positive integers is $$2^n-1$$, and $$\max S(A)=\max A$$.

Now suppose that $$A=\{a_n:n\in\Bbb Z^+\}$$, where $$a_n for each $$n\in\Bbb Z^+$$. For $$n\in\Bbb Z^+$$ let $$A_n=\{a_k\in A:1\le k\le n\}$$. Then each $$m\in S(A)$$ is uniquely $$A$$-expressible iff $$|S^+(A_n)|=2^n-1$$ for each $$n\in\Bbb Z^+$$. Moreover, $$S^+(A)=\Bbb Z^+$$ iff for each $$k\in S^+(A)$$ there is a minimal $$n(k)\in\Bbb Z^+$$ such that $$k\in S^+(A_{n(k)})$$. Note that either $$n(k)=1$$, or $$k\in S^+(A_{n(k)})\setminus S^+(A_{n(k)-1})=\{a_{n(k)}-s:s\in S^+(A_{n(k)-1})\}$$.

For $$n\in\Bbb Z^+$$ let

$$a_n=2^n-1=\underbrace{1\ldots 1}_n\text{ in binary},$$

and let $$A=\{a_n:n\in\Bbb Z^+\}$$. It’s not hard to see that

$$S^+(A_n)=\{1,\ldots,2^n-1\}$$

for each $$n\in\Bbb Z^+$$, so $$A$$ is, as you already observed, an alt-basis. For instance, working in binary, we see that

\begin{align*} 22&=10110_{\text{two}}\\ &=11111_{\text{two}}-1111_{\text{two}}+111_{\text{two}}-1_{\text{two}}\\ &=31-15+7-1\\ &=a_5-a_4+a_3-a_1. \end{align*}

Now let $$\ell,m\in\Bbb Z^+$$. For $$n=1,\ldots,\ell$$ let

$$\color{red}{a_n^{(\ell,m)}}=2^ma_n=\underbrace{1\ldots 1}_n\underbrace{0\ldots 0}_m\text{ in binary}.$$

For $$n=\ell+k$$, where $$k=1,\ldots,m$$, let

$$\color{blue}{a_n^{(\ell,m)}}=2^{m-k}a_n=\underbrace{1\ldots 1}_n\underbrace{0\ldots 0}_{m-k}\text{ in binary}.$$

Finally, for $$n>\ell+m$$ let $$a_n^{(\ell,m)}=a_n$$, and let $$A_{(\ell,m)}=\left\{a_n^{(\ell,m)}:n\in\Bbb Z^+\right\}$$; then $$A_{(\ell,m)}$$ is an alt-basis.

For example,

\begin{align*} A_{(4,2)}&=\{\color{red}{4},\color{red}{12},\color{red}{28},\color{red}{60},\color{blue}{62},\color{blue}{63},127,\ldots\}\\ &=\{\color{red}{100},\color{red}{1100},\color{red}{11100},\color{red}{111100},\color{blue}{111110},\color{blue}{111111},1111111,\ldots\}\text{ in binary}. \end{align*}

To verify this it suffices to show that $$S^+\left(\left\{a_n^{(\ell,m)}:1\le n\le \ell+m\right\}\right)=S^+(A_{\ell+m})$$. The argument is a bit messy to write out, but the idea is straightforward; I’ll illustrate it with $$A_{(4,2)}$$. First, it’s clear from the discussion of $$A$$ that

\begin{align*} S^+\left(\{4,12,28,60\}\right)&=S^+\left(4\{1,3,7,15\}\right)\\ &=4S^+\left(\{1,3,7,15\}\right)\\ &=4\{1,2,\ldots,15\}\\ &=\{4,8,12,\ldots,60\}\\ &=4S^+(A_4). \end{align*}

Then

\begin{align*} S^+(\{4,&12,28,60,62\})=\\ &4S^+(A_4)\cup\left\{|62-s|:s\in S^+(\{4,12,28,60\})\right\}\cup\{62\}=\\ &4S^+(A_4)\cup\left\{|62-s|:s\in\{4,8,12,\ldots,60\}\right\}\cup\{62\}=\\ &4S^+(A_4)\cup\{2,6,10,\ldots,58,62\}=\\ &\{2,4,6,8,\ldots,60,62\}=\\ &2S^+(A_5), \end{align*}

and a similar calculation shows that $$S^+(\{4,12,28,60,62,63\})=S^+(A_6)$$.

I did not collect the set of all alt-bases, but I did find some useful observations, including:

Alt-basis must contain an infinite number of terms of form $$a_k=2^{k}-1,k\in N\subseteq\mathbb N$$.

The converse does not hold. At the end, I give examples of alt-bases and not-alt-bases in this context.

Do correct me If I missed anything.

Let $$A=\{a_1,a_2,\dots\}$$ such that $$a_1\lt a_2 \lt \dots$$ are positive integers.

Definition. For $$A$$ to be an "alt-basis", we need to have both the "uniqueness" and "completeness". In other words, every number is expressible in exactly one way via alternating summation of subsets of $$A$$, which are summed in increasing order.

Definition. A finite (sub)sequence $$A|_n=\{a_1,\dots,a_n\}$$ is an "alt-prefix" if every integer in $$[1,2^{n}-1]$$ is uniquely expressible via alternating summation of subsets of $$A|_n$$ when summed in increasing order. The element $$a_n$$ is called an "anchor element".

Definition. "Anchor sequence" is a set $$\mathcal A(A):=\{a_{n_1},a_{n_2},\dots\}$$ of all "anchor elements" $$a_{n_1},a_{n_2},\dots$$

Notice that a set has $$2^n$$ subsets minus the empty set and that every subset can be rearranged in an increasing order. We want to assign a distinct value to each of those subsets via the alternating summation, to have an alt-basis. The alt-prefix is defined to cover exactly those $$2^n-1$$ subsets. It follows that:

Lemma. $$A$$ is an alt-basis $$\iff$$ $$A$$ is a union of alt-prefixes $$A=A|_{n_1}\cup A|_{n_2}\cup \dots$$

That is, $$A$$ is an alt-basis if and only if there exists a corresponding infinite anchor sequence $$\mathcal A(A)$$.

We add two more definitions to write all of this more easily:

Definition. Let $$s(\{b_1,\dots,b_n\})$$ be the result of the alternating summation of $$b_1\lt b_2\lt \dots\le b_n$$. Let $$s_+$$ and $$s_-$$ always start the alternating summation with $$+,-$$ respectively. Then $$s_+=-s_-$$. If $$n$$ is odd then $$s=s_+$$ and if $$n$$ is even then $$s=s_-$$. This guarantees $$s\gt 0$$ because the largest element $$b_n$$ will have a positive sign.

Definition. Define "$$n$$-th partial subset-sum set" of a positive increasing integer sequence $$A$$ as:

$$\mathcal S_n(A):=\{s(A_i):A_i\in\mathcal P(A|_n)\}$$

Where $$\mathcal P(A|_n)$$ is the set of all subsets of $$A|_n=\{a_1,a_2,\dots,a_n\}$$.

The set of all "anchor elements" $$\mathcal A(A)=\{a_{n_1},a_{n_2},\dots\}\subseteq A$$ satisfies $$S_{n_i}=[1,2^{n_i-1}-1]$$ for all $$n_i$$.

Corollary. $$A$$ is an alt-basis if and only if it "is covered by the anchor sequence": $$\max \mathcal A(A)\to \infty$$.

Notice that $$\max S_n = a_n$$. If $$a_n$$ is an anchor element, then $$\max S_n = 2^n-1$$. This gives:

Proposition. If $$a_n$$ is an anchor element, then $$a_n=2^n-1$$.

The converse does not hold. For example, in $$\{1,4,7\}$$ the $$a_3=7=2^3-1$$ but $$a_3$$ is not an anchor element, because $$S_3=\{1,3,4,6,7\}\ne[1,7]$$.

Example $$1$$. It is not hard to see that $$\mathcal A(\{2^n-1\})=\{2^n-1\}$$. This is because:

• $$S_1=\{(+1)\}$$ $$\implies$$ $$a_1$$ is an anchor element.

• $$S_2=\{(+1),(-1+3),(3)\}$$ $$\implies$$ $$a_2$$ is an anchor element.

• $$S_3=\{(+1),(-1+3),(3),(-3+7),(+1-3+7),(-1+7),(7)\}$$ $$\implies$$ $$a_3$$ is an anchor element.

• $$\dots$$ proceed via induction to show every $$a_n$$ is an anchor element.

Since $$\mathcal A(\{2^n-1\})$$ exists and covers the entire $$\{2^n-1\}$$, the $$\{2^n-1\}$$ is an alt-basis.

Example $$2$$. The $$\mathcal A(\{n\})=\{1\}$$ does not cover the entire $$\{n\}$$, hence $$\{n\}$$ is not an alt-basis.

It is not hard to see that $$\max S_n = n \lt 2^n-1\implies a_n$$ is not an anchor element, for every $$n\gt 1$$.

Example $$3.$$ We construct an alt-basis where every $$2$$nd element is an anchor element.

$$A=\begin{cases} 2^n-1, & n\text{ is even} \\ 2^n+2^{n-1}-1, & n\text{ is odd} \end{cases}$$

Use an inductive argument. Assume $$n=2k$$, $$a_{n}=2^{n}-1$$ is an anchor element, which means we have uniquely constructed all $$I_0=[1,2^n-1]=S_{n}$$ elements. Now we can subtract numbers in this interval from $$a_{n+1}$$ to see that:

• $$a_{n+1}=2^{n+1}+2^{n}-1$$ will cover $$I_1=[a_{n+1}-a_{n}, a_{n+1}]=[2^{n+1},2^{n+1}+2^{n}-1]$$

Here we see that $$I_0\cup I_1 \ne [1,2^{n+1}-1]$$ $$\implies$$ $$a_{n+1}$$ is not an anchor elemetn.

To see that $$a_{n+2}=2^{n+2}-1$$ is an anchor element, lets see what will we cover with it:

• $$a_{n+2}$$ combined with $$I_0$$ will cover $$I_2=[a_{n+2}-a_{n}, a_{n+2}]=[2^{n+1}+2^{n},2^{n+2}-1]$$

• $$a_{n+2}$$ combined with $$I_1$$ will cover $$I_3=[a_{n+2}-a_{n+1},a_{n+2}-2^{n+1}]=[2^n,2^{n+1}-1]$$

Now observe $$I=I_0\cup I_3\cup I_1\cup I_2$$ is equal to:

$$I=[1,2^n-1]\cup[2^n,2^{n+1}-1]\cup[2^{n+1},2^{n+1}+2^{n}-1]\cup[2^{n+1}+2^{n},2^{n+2}-1]=[1,2^{n+2}-1]$$

Implying $$a_{n+2}$$ covers $$I=[1,2^{n+2}-1]=S_{n+2}$$, $$\implies$$ $$a_{n+2}$$ is an anchor.

It is not hard to check base cases $$n=1,2$$, and we are done. We have:

$$\mathcal A\left(\left.\begin{cases} 2^n-1, & n\text{ is even} \\ 2^n+2^{n-1}-1, & n\text{ is odd} \end{cases}\right\}\right)=\{2^{2n}-1\}$$

So we have an alt-basis $$A$$.

Example $$4$$. It is not hard to show that:

$$A=\{2^k,2^k+1,2^k+3,2^k+7,\dots,2^k+2^{k}-1,2^{k+2}-1,2^{k+3}-1,\dots\}$$

Is an alt-basis for every $$k=0,1,2,\dots$$, whose anchors are all elements $$a_n,n\gt k$$.

Example $$5$$. The sequence of natural, triangular, tetrahedral,... numbers, or in general, any diagonal of the pascals triangle, is not an alt basis.

This is because for every fixed $$d$$, there exists $$n_0$$, such that for all $$n\ge n_0$$, we have $$\binom{n+d-1}{d}<2^n$$ implying that $$\max S_n\lt 2^n-1$$ for all $$n\ge n_0$$. This implies the sequence of anchors has at most $$n_0$$ elements, implying $$\max\mathcal A(A)\lt \infty$$, hence we do not have an alt-basis becuase of inevetable duplicates.

• I think => part of the initial lemme requires proof. – balcinus Mar 31 at 10:07