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

  • 2
    [Basis Representation Theorem](http://www.proofwiki.org/wiki/Basis_Representation_Theorem)2012-01-16
  • 0
    @pedja Alas, that proof obscures the essence of the matter.2012-01-16
  • 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#30173682018-11-29

4 Answers 4

0

The existence and uniqueness theorem 3.1.1, on $\text{base-b} \ge 2$ expansions does not include a proof. Here we supply a formal argument for the case of binary expansions.

Lemma 1: There exists one and only one way to express the integer $n \ge 0$ in the form

$\tag 1 n = m + 2^k \text{ where } \, 0 \le m \lt 2^k$
Proof
There exists a smallest integer $k \ge 0$ such that $n \lt 2^{k+1}$, so we can set $m = n - 2^{k}$ and get the existence for a (1) representation.
Suppose now that $n$ has a (1) representation. If we can show that $n \lt 2^{k+1}$, then one can easily conclude the uniqueness. But,

$\quad n = m + 2^k \lt 2^k + 2^k = 2 \times 2^k = 2^{k+1} \qquad \blacksquare$

Observe that we do not have to rely on reductio ad absurdum in this proof.

Proposition 2: Binary representation exist and are unique.
Proof
Just keep applying (1), peeling off unique descending $k^{'}\text{s}$. The corresponding $m^{'}\text{s}$ eventually hit $0$, and then the algorithm is complete. $\qquad \blacksquare$

Example: Get the binary expansion of $42_\text{ base 10}$.

$42 = 10 + 2^5$
$10 = 2 + 2^3$
$2 = 0 + 2^1$

Answer: 101010

Note that this 'top down' approach is different from the solution for example 3.2.1 found in the OP's link. It appears that using this technique we can bypass the 'bottom up' Euclidean algorithm. It should also work for other bases, but then you have to get the corresponding 'base digit' to go with the '$k$ positional placement' in the expansion.

Computers have more fun ... or do they?

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

  • 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$...2012-01-17
  • 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
    I don't understand how "arised iteratively" helps in the proof.2012-01-17
  • 0
    @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$2012-01-17
  • 0
    OK, did we do the induction portion, cause I'm a bit lost on organizing it2012-01-17
  • 0
    @Buddy I edited my post to give a sketch of the inductive proof.2012-01-17
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.