Prove by induction that every positive integer is represented by some binary number?

Question

A binary number is a string $r_mr_{m-1} \cdots r_1r_0$ where $m \in \mathbb{N}$ and $r_i \in \{0,1\}$ for $i=0,\ldots,m$. The string represents the positive integer $r_m2^m+r_{m-1}2^{m-1}+\cdots+r_12+r_0$. Prove by induction that every positive integer is represented by some binary number.

How do I prove p(x),p(k) and p(k+1). Or Strong induction?

Answer 1

Proof by strong induction:

Base case: 1 can be written in binary as 1

Assume that $P(n)$ is true i.e. for all $m$ such that $ 0 \leq m \leq n$, we can represent $m$ in binary.

Now consider an integer $n+1$. We need to prove that we can represent $n+1$ in binary. We can write $n+1$ as $2m$ or $2m + 1$ for some integer $m$ where $m < n$. By strong induction, we know $m$ has a binary representation $r_mr_{m-1} \cdots r_1r_0$ and so $2m$ has representation $r_mr_{m-1} \cdots r_1r_00$ and we can add either 0 or 1 to this depending on whether $n+1 = 2m$ or $n+1 = 2m+1$.

Thus if we can represent all integers less than $n+1$, we can also represent $n+1$.

Answer 2

Clever use of strong induction:

Asume true for $0 \le n < 2^k$:

Then we can prove it is true for $2^k \le n+ 2^k < 2^k+2^k=2^{k+1} $

by simply writing $1xxxxxx... = 2^k + xxxxx.... = 2^k+ n$ where $xxxxx.... =n $ in binary.

That's the induction step.

The base step is $0=0$ and $1=2^1-1$.