# Binary expansion Unique

I am trying to show that how the binary expansion of a given positive integer is unique.

According to this link, http://www.math.fsu.edu/~pkirby/mad2104/SlideShow/s5_3.pdf, All I see is that I can recopy theorem 3-1's proof?

Is this polished enough of an argument. Thanks

-
Basis Representation Theorem – pedja Jan 16 '12 at 9:38
@pedja Alas, that proof obscures the essence of the matter. – Bill Dubuque Jan 16 '12 at 19:41

Assume for contradiction that $n$ is the smallest positive integer with two different binary expansions.

Then $n=a_m\dots a_0=b_m\dots b_0$, allowing leading zeroes in at most one of the expansions.

Let $l$ be the smallest index so that $a_l\neq b_l$. It follows that $a_m\dots a_l = b_m\dots b_l$ are distinct representations of the same number. $l$ must be $0$ due to minimality of $n$, but then our original number would be both odd and even, contradiction.

-

Assume by contradiction that a number $n$ has two different binary expansions.

Then $n=a_m...a_0=b_k...b_0$.

Let $l$ be the smallest index so that $a_l \neq b_l$. It follows that the binary numbers $a_{l-1}...a_1a_0=b_{l-1}...b_1b_0$. By subtracting these from $n$ we get

$$a_m...a_l00000..0=b_k...b_l0000...0 \,.$$

Now $a_l\neq b_l$ means that one of these is $0$ and the other is $1$. But then, one side ends in at least $l+1$ zeroes, meaning is divisible by $2^{l+1}$, while the other ends in exactly $l$ zeroes, meaning is not divisible by $2^{l+1}$.

This contradicts the fact that they are equal....

-
BTW, the last step seems to rely on the fact that we are in basis 2, since i used the fact that if two binary digits are different one must be 0... But it is not, if you work in a different basis, and the last digits $a_l, b_l$ are different, than by subtracting $a_l$ from both you can make one of them $0$... – N. S. Jan 17 '12 at 17:07
Perhaps the best answer in my opinion, but I don't see how $l$ leading zeros means the number is divisible by $2^{l}$. Please provide some theorem or example, if possible. – dotslash Dec 15 '13 at 11:11

Hint $\$ Put $\ b_i = 2\$ in this sketched proof of the uniqueness of mixed-radix representation

$$\begin{eqnarray} n &=& d_0 +\ d_1\, b_0 +\ d_2\, b_1\,b_0 +\ d_3\, b_2\,b_1\,b_0 +\ \cdots, \quad 0 \le d_i < b_i,\ \ b_i > 1\\[0.1em] &=&c_0\, +\, c_1\, b_0 +\, c_2\,\, b_1\,b_0 + \, c_3\,\, b_2\,b_1\,b_0 +\ \cdots, \quad 0 \le c_i < b_i\end{eqnarray}$$

$\, c_0 = d_0\$ since $\,{\rm mod}\ b_0\!:\ c_0 \equiv n\equiv d_0\,$ and $\ 0 \le c_0,d_0 < b_0.\,$ Now induct on smaller tails

$$\begin{eqnarray} (n-d_0)/b_0 &=& d_1 +\ d_2\, b_1 +\ d_3\, b_2\, b_1 + \ \cdots\\[0.1em] =\, (n-c_0)/b_0 &=& c_1 +\, c_2\,\, b_1 +\ c_3\ b_2\, b_1 + \ \cdots \end{eqnarray}$$

$(n-d_0)/b_0 \le\, n/b_0 <\, n\$ by $\,d_0 \ge 0,\ b_0 > 1,\,$ so by induction $\ c_i = d_i\$ for $\,i \ge 1.$

-
I don't understand how "arised iteratively" helps in the proof. – Buddy Holly Jan 17 '12 at 5:29
@Buddy Iteration = induction. The first digit $\rm\:d_0\:$ is unique because it is $\rm\:n\ mod\ b\:.\:$ The remaining digits are unique by induction applied to $\rm\:(n-d_0)/b\ =\ d_1 + d_2\ b +\:\cdots$ – Bill Dubuque Jan 17 '12 at 5:52
OK, did we do the induction portion, cause I'm a bit lost on organizing it – Buddy Holly Jan 17 '12 at 6:48
@Buddy I edited my post to give a sketch of the inductive proof. – Bill Dubuque Jan 17 '12 at 17:03