# Proving binary integers

This is a very interesting word problem that I came across in an old textbook of mine. So I know its got something to do with binary integers (For ${0, 1, 2, 3}$ we have the representations $0, 1, 10, 11$), but other than that, the textbook gave no hints really and I’m really not sure about how to approach it.

Any guidance hints or help would be truly greatly appreciated. Thanks in advance ðŸ™‚ So anyway, here the problem goes:

Prove by induction that
all integers can expressed as a sum of some powers of two.
(i.e. that they have a representation in base $2$.)

#### Solutions Collecting From Web of "Proving binary integers"

The base case is $n=0$, which has binary representation $0_2$.

For the induction step, assume that all integers less than $n$ have a binary representation.

Write $n=2m+r$, with $r=0$ or $r=1$. By induction, $m=(b_k \cdots b_1 b_0)_2$. Thus, $n=(b_k \cdots b_1 b_0r)_2$.

This is one example that induction from $n$ to $n+1$ is messy but induction from $m<n$ to $n$ is easy.

WLOG we can prove this for positive integers, for negative integers we can negate the representation of its absolute value and $0$ is trivial case.
Let’s prove that every integer between $[2^n,2^{n+1}]$ can be represented in binary format. The base case is $[1,2]$. So by induction we know that $[1,2^n-1]$ can be represented.
Then $x \in [2^n,2^{n+1}]$ and it’s easy to see that $x \lt 2^{n+1}$ (if $x=2^{n+1}$ it’s trivial) implies $x-2^n \lt 2^n$.
$x-2^n$ can be represented in binary, by hypothesis. Then the representation for $x$ in binary is $(x-2^n) + 2^n$.