0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.