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$.)
Best Answer
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.