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'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:

$<2^s$

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|improve this question
1  
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
add comment

1 Answer 1

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|improve this answer
    
Very nicely explained! Thanks a lot. :) –  dotslash Dec 15 '13 at 15:06
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.