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.
Best Answer
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<a_{n+1}$ 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)$.