"Concrete Mathematics" book I don't understand radix 2 explanation for Josephus problem

Question

I started reading the book Concrete Mathematics 2nd edition and there is a conversion I don't understand(is in page 11 of the book), it says:

Powers of 2 played an important role in our nding the solution, so it's natural to look at the radix 2 representations of $n$ and $J(n)$. Suppose $n$'s binary expansion is

$n = (b_m b_{m-1} ... b_1 b_0)_2$;

that is,

$n = b_m2^m + b_{m-1}2^{m-1} + · · · + b_{1}2 + b_0;$

So far this part is clear to me, is the classic binary notation: $1\cdot 2^0+0\cdot 2^1+1\cdot 2^2+\cdots$

where each $b_i$ is either $0$ or $1$ and where the leading bit $b_m$ is 1. Recalling that $n = 2^m + l$, we have, successively,

$n = (1 b_{m-1} b_{m-2} ... b_1 b_0)_2 ;$

$l = (0 b_{m-1} b_{m-2} ... b_1 b_0)_2 ;$

$2l = (b_{m-1} b_{m-2} ... b_1 b_0 0)_2 ;$

$2l + 1 = (b_{m-1} b_{m-2} ... b_1 b_0 1)_2 ;$

$J(n) = (b_{m-1} b_{m-2} ... b_1 b_0 b_m)_2 :$

These are the inductions I just don't get, I don't see the explanation to those ones and zero values $n$, $L$, $2L$ and $2L+1$

Answer 1

• $n = (1 b_{m-1} b_{m-2} ... b_1 b_0)_2$: the hypothesis is that the leading bit is $1$.
• $l = (0 b_{m-1} b_{m-2} ... b_1 b_0)_2$: by definition $n=b^m+l$, and, writing this in base $2$, we have $$(1 b_{m-1} b_{m-2} ... b_1 b_0)_2=\underbrace{(1 0 0 ... 0 0)_2}_{=b^m}+\underbrace{(0 b_{m-1} b_{m-2} ... b_1 b_0)_2}_{\text{so this is }\: l}$$
• $2l = (b_{m-1} b_{m-2} ... b_1 b_0 0)_2$: multipliying by the base amounts so shifting the bits one step on the left (just like multiplying by $10$ in the decimal system is done by adding a final $0$.
• $2l + 1 = (b_{m-1} b_{m-2} ... b_1 b_0 1)_2$: $$2l+1=(b_{m-1} b_{m-2} ... b_1 b_0 0)_2+ (00 ... 0 01)_2.$$

Is it clearer?

Answer 2

The bits for $n$ reflect the fact that the leading bit must be a $1$ or we would have a shorter number. It is like not writing $2$ in base $10$ as $02$. That $1$ is in the $2^m$ place, so we can subtract $2^m$ from $n$ to get $l$ and have $l$ look just like $n$ except the leading $1$ is deleted. That can result in leading zeros in $l$. Multiplying by $2$ in base $2$ just appends a zero on the right, which is the source of the $2l$ equation. As $2l$ is even, it has a $0$ in the ones bit so we can add $1$ without carrying, which is the source of the $2l+1$ equation. You have not defined $J(n)$ so I can't help there.

Answer 3

$$n = 2^m+l\tag{1}$$ where $2^m$ is the largest power of $2$ not exceeding $n$.

It results then $$l<2^m$$ Now, from $(1)$ and $n=b_m2^m+b_{m-1}2^{m-1} + \dots+b_0$, it follows that $$b_m2^m+b_{m-1}2^{m-1} + \dots+b_0=2^m+l$$ that splits into: \begin{equation} \begin{cases} b_m2^m=2^m\\ b_{m-1}2^{m-1} + \dots+b_0=l \end{cases} \implies\\\implies\begin{cases} b_m=1\\ 2l+1=\color{blue}2(b_{m-1}2^{m-1} + \dots+b_0)\color{blue}{+1}=b_{m-1}2^m + \dots+b_02+1 \end{cases} \end{equation} that joins into $$2l+1=b_{m-1}2^m + \dots+b_02+b_m$$

But $J(n)=2l+1$, then $$J(n)=b_{m-1}2^m + \dots+b_02+b_m$$