2
$\begingroup$

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

  • 0
    For more answers, see the duplicate at https://math.stackexchange.com/questions/3017323/is-there-an-easy-way-to-see-that-binary-expansion-is-unique/3017368#30173682019-02-02

3 Answers 3

2

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.

3

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

  • 0
    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.2013-12-15
2

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

  • 0
    @Buddy I edited my post to give a sketch of the inductive proof.2012-01-17