Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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'm having trouble understanding this proof of uniqueness of binary representation of integers:

Suppose there exists an integer $n$ with two different binary representations. Let these be:

$$2^r + c_{r-1}\cdot2^{r-1} + \cdots + c_1 \cdot 2 + c_0 = 2^s + d_{s-1}\cdot2^{s-1} + \cdots + d_1 \cdot 2 + d_0$$ where $c_i, d_i$ are either $1$ or $0$.

Without loss of generality, assume that $r<s$.

Now, $2^r + c_{r-1}\cdot2^{r-1} + \cdots + c_1 \cdot 2 + c_0 \leq 2^r + 2^{r-1} + \cdots + 2 + 1$

= $2^{r+1}-1$ (summing the geometric series)

Now the book throws the bouncer:


And then goes on to show that the first number is less than the second, which is a contradiction. I'm stumped as to how $2^{r+1} - 1 < 2^s$, when we have no definite information about $r$ and $s$. For all we know, maybe $s$ is less than twice of $r$.

Please help.

share|cite|improve this question
When $s>r$ then $s\geq r+1$ and therefore $2^s\geq 2^{r+1}>2^{r+1}-1$. – Christian Blatter Dec 15 '13 at 12:43
@ChristianBlatter Excellent! Thank you very much! – dotslash Dec 15 '13 at 13:14
up vote 1 down vote accepted

More generally, we can show uniqueness with respect to any basis $b>1$ (integer).

Suppose $n=x_0+x_1b+x_2b^2+\dots+x_rb^r=y_0+y_1b+y_2b^2+\dots+y_sb^s$, where $0\le x_i<b$ and $0\le y_j<b$, but $x_r\ne0$ and $y_s\ne0$.

First of all, we must have $r=s$. Otherwise, suppose $r>s$; then $$ x_0+x_1b+x_2b^2+\dots+x_rb^r\ge x_rb^r\ge b^{r} $$ and $$ y_0+y_1b+y_2b^2+\dots+y_sb^s<b^{s+1}\le b^r, $$ a contradiction. Why $y_0+y_1b+y_2b^2+\dots+y_sb^s<b^{s+1}$? Prove it by induction.

So $r=s$. Consequently, $x_0=y_0$, because this is the remainder of the division of $n$ by $b$. The conclusion follows by induction, because we have $$ b(x_1+x_2b+\dots+x_rb^{r-1})=b(y_1+y_2b+\dots+y_rb^{r-1}) $$

share|cite|improve this answer
Very nicely explained! Thanks a lot. :) – dotslash Dec 15 '13 at 15:06

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.