2

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

anonymous
  • 2,423
  • You should say all integers $> 0$ because obviously 0 and the negative integers do not have this property. – gammatester Jun 19 '15 at 11:24
  • 1
    Does the question actually specify that the powers of two are distinct? Otherwise, $1$ is a power of two, and $1 + 1 + 1 + 1 + \cdots + 1$. – Erick Wong Jun 19 '15 at 22:56
  • 1
    @ErickWong Yes, it actually specifies that the powers of two are distinct. And no, $1$ being a power of two is not valid. – anonymous Jun 19 '15 at 23:02
  • @anonymous Note that your question does not specify this. Of course $1$ is a power of two, otherwise how could you represent any odd number?? – Erick Wong Jun 19 '15 at 23:06

2 Answers2

3

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.

lhf
  • 216,483
0

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

JukesOnYou
  • 616