# Understanding the odd case of proving by induction the binary representation of any natural number

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.