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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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
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
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|cite|improve this answer
Probably want $(-2)^{-i}$, since otherwise there's trouble with e.g. $111\ldots$ and $10111\ldots$ which diverge. – Rebecca J. Stones 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

Your Answer


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.