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


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


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