Binary representation of a number $n$ with exactly one leading 0 can be turned into a binary representation of $n+1$

Question

Prove that for $\forall n \in \mathbb{N}$, the binary representation of $n$ with exactly one leading 0 can be turned into a binary representation of $n + 1$ by flipping exactly one bit from 0 to 1, and some number of bits from 1 to 0. For example, the binary representation ofn=7 with one leading 0 is 0111, andn=8 has a binary representation 1000. Only one bit,d3, flips from 0 to 1.

My thoughts are to use induction, and then for the induction part, I want to split it into even and odd, but then I don't know what to do.

Answer 1

HINT: Let $b_kb_{k-1}\ldots b_0$ be the binary representation of an $n$ with exactly one leading zero (so $b_k=0$ and $b_{k-1}=1$). Let $m$ be the smallest non-negative integer such that $b_m=0$; clearly $0\le m\le k$. Show that $n+1$ has the binary representation $b_k'b_{k-1}'\ldots b_0'$, where

$$b_i'=\begin{cases} b_i,&\text{if }m<i\le k\\ 1,&\text{if }i=m\\ 0,&\text{if }0\le i<m\,. \end{cases}$$

Answer 2

Hint

If the binary representation of $\ n\ $ terminates with exactly $\ k\ $ $1$s preceded by a $0$, then the binary representation of $\ n+1\ $ must terminate with exactly $\ k\ $ $0$s preceded by a $1$.

Answer 3

I'm not sure if I understand correctly. If the binary representation of a number $n$ is $011...11$ (with $k$ digits) then $n = 2^ {k-1} - 1$. When you change the leading $0$ for $1$ and all $1$'s for $0$'s you obtain $100.. 00$ which is $2^{k-1}$.