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.
Best Answer
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}$$