Is there an easy way to see that binary expansion is unique? [duplicate]

Let $n \in \mathbb{N}$. Using the Euclidean algorithm, it is straightforward to see that every natural number can be written as

$$n = \sum_{j=0}^m \epsilon_j(n) 2^j $$

where $\epsilon_j(n) \in \{0,1\}$.

Is there an easy way to show that this way of writing the number is unique?

Solution 1:

How do you know the ordinary base $10$ expansion is unique?

Suppose digit strings $s$ and $t$ both represent the positive integer $n$. Then the units digit of each must be $d = n \pmod {10}$. So you can lop off both units digits. The lopped strings then both represent $(n-d)/10$.

Continue with the other digits (from the right) until you're done. Or, for a formal induction proof, apply that argument to the least $n$ with two representations to deduce a contradiction.

This argument works for any base. It's the standard algorithm for base conversion, finding the digits from right to left. It depends on knowing that you can do division with remainder, but not on the full strength of the Euclidean algorithm.

Solution 2:

Suppose $\exists n\in\Bbb N$ such that $n=\sum_{i\in A}2^i=\sum_{i\in B}2^i$ with $A,B\subset\Bbb N_0$. Then $\sum_{i\in A}2^i-\sum_{i\in B}2^i=0$ and so for set $C=A\Delta B$ (symmetric difference) and some function $s:C\rightarrow\{-1,1\}$ we have $\sum_{i\in C}s(i)2^i=0$. Now if $C\ne\emptyset$ then $C$ has a largest element (say $x$) and we have $\sum_{i\in C\backslash\{x\}}s(i)2^i=-s(x)2^x$ so $\sum_{i\in C\backslash\{x\}}-{s(i)\over s(x)}2^i=2^x$ but we now know $C\backslash\{x\}\subset\{0,1,2,...,x-1\}$ and also $-{s(i)\over s(x)}\le1$ so we have $\sum_{i\in C\backslash\{x\}}-{s(i)\over s(x)}2^i\le\sum_{i=0}^{x-1}2^i=2^{x}-1$ which is a contradiction. Hence $C=\emptyset$, so $A=B$, so the representations are in fact the same, hence the representation of n is unique (assuming it exists, which I gather has been shown already).

Solution 3:

A very simple proof is by the pigeonhole principle. The key observation is that not only does any natural number $n$ have a binary expansion $$n = \sum_{j=0}^m \epsilon_j(n) 2^j,$$ but if $0\leq n<2^N$ then we need no powers of $2$ above $2^{N-1}$ so we can take $m=N-1$. Now, for any fixed $N$, there are $2^N$ natural numbers $n$ such that $0\leq n<2^N$ and $2^N$ different ways of choosing $\epsilon_j(n)\in\{0,1\}$ for each $j$ from $0$ to $N-1$. So, all $2^N$ of these binary expansions must have distinct sums, or else they would not be able to represent all $2^N$ of the different values of $n$.

This proves that for any $N$, a natural number $n$ has at most one binary expansion using powers of $2$ up to $2^{N-1}$. It follows that $n$ has only one binary expansion, up to adding $0$s at the start (since given two expansions of different lengths, you can always extend one by $0$s to make them the same length, and then they must become the same).

Solution 4:

Not really an answer. But here's just a different way of framing your question which I think is neat.

Let $f: P_{fin}(\mathbb{N}) \to \mathbb{N}$ by $f(S) =\sum_{s\in S} 2^s$.

$f$ is onto. You have claimed this can be handled Euclidean algorithm.

What about $1-1$? We use the argument Stanley Dodds presented.

So we've seen that the set of all finite subsets of the natural numbers is in 1-1 correspondence with the set of natural numbers.