There are multiple posts here (e.g., 1, 2, 3, 4, each has a different phrasing of what needs to be proved) that explain how to prove by induction that any natural number has a binary representation.

I read all of them, but still can't understand the odd case when proving by induction from $n$ to $n+1$.

I'd like to use here the pharsing of no. 4 above (with a small omission):

For every number n $\in N^+ $, there is a unique representation of n in the form $\sum_{i=0}^{p}b_i2^i$ where [...] p is non-negative, and $b_p,b_{p-1}....b_0 > \in$ {0,1}

And let's also take this answer, which reflects in its concise form many other similar answers:

If it is true for $m\leq n$, $n=\sum a_i2^i$, $n+1=\sum a_i2^i+1$, if $a_0=0$ done, if not $n+1$ is even and $(n+1)/2=\sum b_j2^j$, you have $n+1=\sum b_j2^{j+1}$.

My question:

I get the even case (i.e., when $n+1$ is even): we manage to have the sigma expression in its original form, that is $\sum_{i=0}^{p}b_i2^i$. But with the odd case, we have a "residual" $+1$, which is not present in the original sigma expression, and thus I don't understand why is that a correct proof.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.