[Math] Alternating sum of positive integers

Question

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.

Can some sequence $\{E\}$ with first term $1$ and second term $4$ be an alt-basis? What terms would this sequence include?

What about another sequence $\{F\}$ with first term $2$ and second term $3$? What terms would this sequence include?

Answer 1

To clarify why @combinatorial609 is correct:

Suppose a positive integer is written as an alternating sum $\pm(2^{i_1}-1)\mp(2^{i_2}-1)\pm\cdots(2^{i_k}-1)$, with $0<i_1<i_2<\cdots< i_k$. Then we must have the sign of $(2^{i_k}-1)$ being $+$, since that term is greater in magnitude than all others put together. So we can rewrite it as $$(2^{i_k}-1)-(2^{i_{k-1}}-1)+\cdots\pm(2^{i_1}-1)=\sum_{j=0}^{i_k-1}2^j-\sum_{j=0}^{i_{k-1}-1}2^j+\cdots\pm\sum_{j=0}^{i_1-1}2^j.$$ Note that on the right-hand side each power of $2$ alternates sign each time it appears, so each power of $2$ appears $0$ or $1$ times in total. All powers from $i_{k-1}$ to $i_k-1$ inclusive appear once, all from $i_{k-2}$ to $i_{k-1}-1$ zero times, and so on. So we can rewrite in binary as the number consisting of 1 $i_k-i_{k-1}$ times, 0 $i_{k-1}-i_{k-2}$ times, and so on down to x $i_1$ times, where x is 1 if $k$ is odd and 0 otherwise. It is clear that every binary representation can be obtained from a unique sequence of $i_j$s in this manner.