Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a problem with proving this thesis:

Notation of a number in base-(-2) numeral system is unambiguous.

I think I need to use mathematical induction, but I don't know how.

share|improve this question
2  
number = real number? natural number? integer? rational number? What? –  GEdgar Sep 10 '13 at 18:59
    
I'm interested in integers. –  ArcCha Sep 10 '13 at 19:05
    
... including negative integers? And "unambiguous" means what? Each number has one and only one way to be written in base $-2$ ? What are the digits you use? –  GEdgar Sep 10 '13 at 19:12
    
Interesting question! Simple topology shows "one and only one expansion" is not true for the reals. So which fails? Some real has no expansion, or some real has two expansions... –  GEdgar Sep 10 '13 at 19:18
1  
I think integers by definition include negative numbers. Yes, "unambiguous" means exactly what you have said. I use "0" and "1". –  ArcCha Sep 10 '13 at 19:18
add comment

1 Answer

up vote 2 down vote accepted

You want to show that if $$\sum_{i=0}^\infty a_i(-2)^i = \sum_{i=0}^\infty b_i(-2)^i$$ are equal, for $a_i, b_i \in {0,1}$, then the coefficients are equal: $a_i=b_i$.

Suppose otherwise, for contradiction, and let $N$ be the highest index for which the two sequences differ (this requires us to assume that both sequences are zero for sufficiently high index, i.e. that the numbers have finitely many non-zero base -2 digits.)

Then $$0 = \sum_{i=0}^N (a_i-b_i)(-2)^i = (a_N-b_N)(-2)^N+\sum_{i=0}^{N-1} (a_i-b_i)(-2)^i.$$

Now $(a_N-b_N)(-2)^N$ is equal to either $2^N$ or $-2^N$ (it can't be zero, by assumption); assume without loss of generality the latter. Then $$0 = -2^N + \sum_{i=0}^{N-1} (a_i-b_i)(-2)^i \leq -2^N + \sum_{i=0}^{N-1} |a_i-b_i|2^i < -2^N + 2^N -1 = -1,$$ a contradiction. So representations in base -2 are unique.

share|improve this answer
    
Probably want $(-2)^{-i}$, since otherwise there's trouble with e.g. $111\ldots$ and $10111\ldots$ which diverge. –  Rebecca Sep 10 '13 at 19:02
    
I was assuming by "number" he meant integers, as it is false for arbitrary real number ($1.101010\ldots = 0.01010101\ldots$). –  user7530 Sep 10 '13 at 19:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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