# Uniqueness proof of binary representation

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$.

-
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

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})$$