Question

Please use high-school math to solve this. I have tried but did not find the solutions.

Answer 1

(a) 

If we take the magnitude of the difference between two consecutive terms in the series we get:

|2ⁿ⁻¹-1-(2ⁿ-1)|=|2ⁿ⁻¹-2ⁿ|=|2ⁿ⁻¹(1-2)|=2ⁿ⁻¹.

All positive integers can be represented by the sum of powers of 2 (this is the basis of the binary system of numbers).

For example, 10=2³+2. But 2³=2⁴-2³=(2⁴-1)-(2³-1)=15-7 and

2=2²-2¹=(2²-1)-(2¹-1)=3-1.

Therefore 10=[2⁴-1)-(2³-1)]+[(2²-1)-(2¹-1)]=15-7+3-1.

Another example:

17=2⁴+2⁰=

(2⁵-2⁴)+(2¹-2⁰).

These correspond to terms:

31-15+1 in D.

Now take 19 as another example: 38=32+4+2=(63-31)+(7-3)+(3-1). In this case -3 cancels +3, and we get (63-31)+(7-1)=32+6=38. This always happens when we have consecutive powers of 2: the negative component of one pair cancels the positive component of the next pair. That is, we get (2ʳ⁺¹-2ʳ)+(2ʳ-2ʳ⁻¹)=2ʳ⁺¹-2ʳ⁻¹=(2ʳ⁺¹-1)-(2ʳ⁻¹-1).

Since every power of 2 can be represented by the difference of two unique consecutive terms in D, and every integer can be represented by the sum of powers of 2, every positive integer is D-expressible uniquely, so D is alt-basis.

(b)

If E={e₁ e₂ e₃ ... eᵣ ...} and eᵣ =r+1, then 1 is not generated uniquely because any consecutive elements differ by 1. Similarly, all other integers are not generated uniquely. So E is not alt-basis: if n is a positive integer then many elements produce the result n, since (r+n)-r=n for all r.

If E was the set of Fibonacci integers {2 3 5 8 13 21...} it would not be alt-basis, because of non-uniqueness; for example: 6=8-2=13-8+3-2.

If the question is to find any E where the first two elements are 2 and 3, a deeper investigation is necessary:

We need to create integers, starting at 1. So we already have 1=3-2 and 2 and 3 are already in E. The next integer is 4 which can’t be produced from 2 and 3. The next element can’t be 4, because 4-3=3-2=1, so 1 is not uniquely generated. So 4 has to be produced another way. If we have 6 as the next element, 6-2=4, but 6-3=3, which is already in E. In other words, there are two ways to produce 3, and 3 is not unique. If the next element is 7, -3+7=4. And 5=-2+7, 6=2-3+7. The next element is 15 (E={2 3 7 15}):

8=15-7, 9=-2+3-7+15, 10=2-7+15, 11=3-7+15, 12=-3+15, 13=-2+15, 14=2-3+15.

If we look at the difference between consecutive elements we get the pattern 3-2=1, 7-3=4, 15-7=8. 

To find e₅, we have to generate the integers from 16 to e₅-1. We might guess that e₅=31, so let’s generate integers from 16 to 30:

16=31-15, 17=-2+3-15+31, 18=2-15+31, 19=3-15+31, 20=-3+7-15+31,

21=-2+7-15+31, 22=2-3+7-15+31, 23=7-15+31, 24=-7+31, 25=-2+3-7+31,

26=2-7+31, 27=3-7+31, 28=-3+31, 29=-2+31, 30=2-3+31

(30=31-1=e₁-e₂+e₅, 29=31-2=-e₁+e₅, 28=31-3=-e₂+e₅, 27=31-4=e₂-e₃+e₅, etc.

           1=-e₁+e₂,                  2=e₁,                   3=e₂,                  4=-e₂+e₃,      etc.)

Comparing this subset of integers with the subset of integers 8-14, a pattern is emerging, so we can guess that e₆=63. To generate the next subset of integers 32-62 we use the integer formation from 1 to 31 as a guide. E={2 3 7 15 31 63 127 ...}. For r>1, eᵣ=2ʳ-1, and e₁=2.

I conclude that this set for E is alt-basis.

(c) F={1 4 6 13 28 59 ...} appears to be alt-basis for similar reasons to those from which the alt-basis E was derived. But we haven’t tested for uniqueness. 3=4-1=6-4+1, so F fails the uniqueness test and F is not alt-basis.

(d) The simple test is to make sure that 1 can be derived (if it’s not part of the set) and all the integers between the first two elements can be derived uniquely when the next element is added.

 

More to follow if there is space for a longer answer...

Comments

Can you list some examples for (d) "the simple test?"

---

 

Let Sᵣ be the alt-basis set {s₁ s₂ ... sᵣ}.

sᵢ₊₁>sᵢ by definition.

Let Zᵨ be the set of ρ integers generated by Sᵣ.

Z₁={a₁ a₂ a₂-a₁}≡{1 2 3}⇒two possible sets:

2.1 S₂={1 3}, Z₃={1 3 2}

2.2 S₂={2 3}, Z₃={2 3 1}

Both Z₃ sets are equivalent (≡) to {1 2 3} so redefine Z₃ as the ordered set of integers. So either S₂ generates just one Z₃. The labels 1.1 and 1.2 show the “family tree” created as we track through all possible alt-basis sets of increasing size.

Next, we need to use Z₃ to create an S which will generate the next Z set of integers.

Add another element s₃ to S₁ to create a set S₃={s₁ s₂ s₃} to generate a Zᵨ={s₁ s₂ s₃ s₃-s₂ s₃-s₁ s₂-s₁ s₃-s₂+s₁}. In this case, we would create Z₇ because there are 7 elements, Z₇={1 2 3 4 5 6 7}. What is the corresponding S₃? We already know s₁ and s₂, which produce the ordered integer set Z₃. S₃ needs to be defined to produce Z₇.

So, unordered, Z₇ can be written:

{s₁ 3 s₃ s₃-3 s₃-s₁ 3-s₁ s₃-3+s₁} where s₁ can be either 1 or 2 depending on which “branch” we take: 2.1 or 2.2:

2.1 Z₇={1 3 s₃ s₃-3 s₃-1 2 s₃-3+1}≡{1 2 3 s₃-3 s₃-2 s₃-1 s₃}≡{1 2 3 4 5 6 7}.

From this s₃=7, and 2.1 S₃={1 3 7}.

2.2 Z₇={2 3 s₃ s₃-3 s₃-2 1 s₃-3+2}≡{1 2 3 s₃-3 s₃-2 s₃-1 s₃}≡{1 2 3 4 5 6 7}.

From this s₃=7, and 2.2 S₃={2 3 7}.

This shows that s₂=3 and s₃=7, with s₁=1 or 2.

Continuing this reasoning we can see that s₄ must be 15:

Z₁₅={1 2 3 4 5 6 7 s₄-7 s₄-6 ... s₄-1 s₄}   

The simple test is that series is S={1 3 7 15 31 ...} or {2 3 7 15 31 ... }. After the first term the other terms are formed by doubling the previous term and adding 1. For n>1, the nth term is 2ⁿ-1. s₁ can be 1 or 2 and to find a particular integer j we need take n terms such that j lies between the (n-1)th and nth terms.