8
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ It seems like it would be very difficult to prove anything is an alt-basis, due to the uniqueness constraint. $\endgroup$ – Wilf Rosenbaum Mar 13 at 6:44
  • 3
    $\begingroup$ Do you know whether there are in fact any alt-bases? If so, could you give us an example? If not, it might make sense to try to answer this more general question first? By the way, what's your motivation for this question? $\endgroup$ – joriki Mar 13 at 6:47
  • 1
    $\begingroup$ For your second bounty-question, isn't $\{2,3,7,15,31,\ldots\}$ an alt-basis for the same reasons as $\{1,3,7,15,31,\ldots\}$? You have only changed the way $1,2,3$ are represented from $(1),(-1+3),(3)$ to $(-2+3),(2),(3)$. $\endgroup$ – Vepir Mar 25 at 20:32
  • $\begingroup$ @Vepir That proves existence -- can you prove uniqueness? $\endgroup$ – combinatorial609 Mar 25 at 20:42
  • $\begingroup$ @combinatorial609 I think it should be inherited from $\{2^n-1\}$ ? Since $\{2^n-1\}$ is an alt-basis, every number has a unique representation $n_i=(\pm n_i^1 \mp n_i^2 \pm \dots)$. If we substitute $(\pm 1\mp \dots),(\mp 1 \pm 3 \mp \dots),(\pm 3 \mp \dots)$ with $(\mp 2 \pm 3 \mp \dots),(\pm 2 \mp \dots),(\pm 3 \mp \dots)$, we didn't change the values of those any $n_i$ representations nor of any of their components $n_i^k$. We didn't have to break the $n_i^{k}\lt n_i^{k+1}$ rule anywhere to substitute this. Hence, our new sequence given those substitutions should remain a valid alt-basis? $\endgroup$ – Vepir Mar 25 at 21:00
7
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Using same reasoning, would 2^n+1 be an alt-basis? $\endgroup$ – TheLeogend Mar 13 at 22:39
  • $\begingroup$ @TheLeogend No, it would very nearly be an alt-basis, but not quite: there is no way to make $1$, but there is a unique way to make every other positive integer. This assumes you start from $n=1$; if you included $n=0$ then you would be able to make $1$, but it would introduce duplicate ways to make some integers (e.g. $4=9-5$ and $4=5-3+2$). $\endgroup$ – Especially Lime Mar 14 at 17:53
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How does one see that this is an alt-basis? I think I can do existence, but I'm not so sure about uniqueness. $\endgroup$ – saulspatz Mar 13 at 7:13
  • 2
    $\begingroup$ I think for this to be an acceptable answer there should be some proof. Maybe I am missing something but it is not obvious to me that every positive integer is uniquely expressible as an alternating sequence of numbers of this form. $\endgroup$ – Wilf Rosenbaum Mar 13 at 7:46
  • $\begingroup$ How do you write 10, for example, as an alternating sequence of elements of this form? How do you know that no other subset of elements also has an alternating sum of 10? $\endgroup$ – Wilf Rosenbaum Mar 13 at 7:56
  • 1
    $\begingroup$ @joriki Surely $6=-1+7$? $\endgroup$ – Especially Lime Mar 13 at 8:36
  • $\begingroup$ @EspeciallyLime: Sorry, I'd erroneously thought the subsequence had to be consecutive. $\endgroup$ – joriki Mar 13 at 9:14
2
+25
$\begingroup$

It is not hard to answer the two additional questions OP poses:

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

This is not possible. The set $\{1,4\}$ generates $1,\_,3,4,\_,\_,\dots=(1),\_,(-1+4),(4),\_,\_,\dots$

Adding $x\gt 4$ as the $3$rd element generates four additional elements: $x,x-1,x-3,x-4$.

The smallest two are consecutive and can never fit inside the singular empty place between $1$ and $3$.

If you want to fill in $2$ with $(n+1)$th element, because of $1$, the largest two elements already generated will always be $a_n-1,a_n$. A consequence is that, the smallest two elements you will be generating at this step are $a_{n+1}-a_n,a_{n+1}-a_n+1$ which are always consecutive. Since the space for $2$ we are filling is surrounded by two already generated values $1,3$, we always have the same problem.

Hence, if you want to represent $2$ by starting with $\{1,4\}$, you are forced to have at least one duplicate representation, violating the uniqueness requirement.

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

The sequence $a_1=2$ and $a_n=2^n-1,n\ge 2$ is an alt-basis: $F=\{2,3,7,15,31,\dots\}$

We have only changed the way $1,2,3$ are represented from $(1),(−1+3),(3)$ to $(−2+3),(2),(3)$ and preserved all the unique representations given by alt-basis $\{2^n-1\}$ (which is a known alt-basis due to another answer on this question.)

Alternatively,

It is not hard to show by induction, that every $a_n,n\ge 2$ of $\{F\}$ is an "anchor element". This implies $\{F\}$ is an alt-basis. See my answer to Aternating sum of an increasing sequence of positive integers for "anchor element", for more information.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.