Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
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

3 Answers 3

up vote 1 down vote accepted

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.

share|improve this answer

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

share|improve this answer
1  
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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.