2

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.

Pythagoras of Samos
  • 1,081
ArcCha
  • 23
  • 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

1 Answers1

2

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.

user7530
  • 49,280
  • 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