# 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 $\rm\ b_i = 2\$ in this sketched proof of the uniqueness of mixed-radix representation

$\rm\qquad\qquad\qquad\qquad n\ =\ d_0 +\ d_1\: b_0 +\ d_2\: b_1\:b_0 +\ d_3\: b_2\:b_1\:b_0 +\ \cdots, \qquad 0 \le d_i < b_i,\ \ b_i > 1$

$\rm\qquad\qquad\qquad\qquad\phantom{n}\ =\ \:\:c_0\: +\ \: c_1\: b_0 +\ \: c_2\:\: b_1\:b_0 +\ \: c_3\:\: b_2\:b_1\:b_0 +\ \cdots, \qquad 0 \le c_i < b_i$

$\rm\: c_0 = d_0\$ since $\rm\:mod\ b_0\!\!\!:\:\ c_0 \equiv n\equiv d_0\:$ and $\rm\ 0 \le c_0,d_0 < b_0\:.\$ Proceed inductively on the rest

$\rm\qquad\qquad\quad\: (n-d_0)/b_0\ = \ d_1 +\ d_2\: b_1 +\ d_3\: b_2\: b_1 + \ \cdots$

$\rm\qquad\quad\:\: =\ (n-\:c_0\:)/b_0\:\ = \ \:c_1\: +\ \:c_2\:\: b_1 +\ \:c_3\:\: b_2\: b_1 + \ \cdots$

Notice $\rm\ (n-d_0)/b_0 \le\: n/b_0 <\: n\$ since $\rm\:d_0 \ge 0,\ b_0 > 1\:.\:$ Hence by induction the above two rep's have equal digits $\rm\ c_i = d_i\$ for $\rm\:i \ge 1\:.\:$ Therefore the above rep's of $\rm\:n\:$ have equal digits. $\$ QED

-
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