Proof/intuition that any non-negative integer can be uniquely expressed in binary form?

Question

How do we know that every non-negative integer can be expressed binarily? And uniquely?

Answer 1

Any integer number $c$ can be written uniquely in any base $b$ representation. For simplicity let's look at non-negative numbers (to extend on negative $n$, just look at the corresponding $-n$ positive number and put a minus sign up front):

$c = \sum a_n b^n, $ where $0 \leq a_n< b$ for $n \in \mathbb{Z}+$.

It is easy to see that there is no alternative representation $c = \sum a_n' b^n$, such that

$0 = \sum a_n b^n - \sum a_n' b^n = \sum (a_n-a_n') b^n$.

Why? Because if $(a_n-a_n') \neq 0 $ for any $n$, then $|(a_n-a_n')| < b$. So $(a_n-a_n')$ cannot be "offset" by either higher (too big) or lower (too small) terms, since $ |(a_{n-1}-a_{n-1}')b^{n-1}| < |(a_n-a_n') b^n| < |(a_{n+1}-a_{n+1}')b^{n+1}| $.

Perhaps the most intuitive proof is devising an explicit algorithm of finding the base $b$ representation:

1. Let's find such $n$ that $c/b^{n+1} < 1$ and $c/b^n \geq 1$. The result of the integer division of $c|b^n = a_n + \text{remainder}$, is our first (nonzero) digit.
2. Now let's take the remainder (which obviously $< b^n$) and divide it by $b^{n-1}$, the result of integer division gives us next digit and so on. Following the process until $n = 0$, it is easy to see that we recover the (unique) representation of $c$ in base $b$.

Now, what's unique about binary representation is that you only have two "digits" 0 and 1, so every power of two is either included or excluded from the representation without any coefficients.

Thus, any (non-negative) integer can be uniquely represented as a sum of distinct powers of 2; remember the note above about extending this proof to negative integers.