Josephus problem, Base 2 reprentration with binomial?

Question

I was reading Josephus problem from book concrete maths (Donald E knuth) and at page 11 he gives the theory below after solving the problem itself (I couldn't understand the below theory and it's following parts...):

Now that we’ve done the hard stuff (solved the problem) we seek the soft: Every solution to a problem can be generalized so that it applies to a wider class of problems. Once we’ve learned a technique, it’s instructive to look at it closely and see how far we can go with it. Hence, for the rest of this section, we will examine the solution (1.9) and explore some generalizations of the recurrence (1.8). These explorations will uncover the structure that underlies all such problems. Powers of 2 played an important role in our finding 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, b,-l . . bl bo)z ; // what is this?

that is,

n = bm2^m + bm-1*2^m-1 + ... + b1*2 + b0, //bm == b sub m

where each bi is either 0 or 1 and where the leading bit b, is 1. Recalling that n = 2”+l , we have, successively,

n = (l*bm-1*bm-2...b1*b0)2,
l = (0*bm-1*bm-2...b1*b0)2 ,
2l = (bm-1*bm-2...b1*b0*0)2,
2l+ 1 = (bm-1*bm-2...b1*b0*1 )2 ,
J(n) = (bm-1*bm-2...b1*b0*bm)2

My question is what are above equation and how did author deduced them?

(I understand binomial this form of binomial I never encountered, also I'm little idiot in maths , so please easy on me and good at explanation)

Answer 1

I think you mean binary not binomial.

$n=(b_mb_{m-1}...b_1b_0)_2$ is just the binary representation of a number. Like you posted it represents $n=b_m2^m+b_{m-1}2^{m-1}+...+b_12+b_0$.

So for an example take n=123, in base 10 we can express this as $$123=1*10^2+2*10^1+3*10^0$$ which is the same as $(123)_{10}$. To express 123 in base 2, we have $$123=1*2^6+1*2^5+1*2^4+1*2^3+0*2^2+1*2^1+1*2^0$$ which is the same as $(1111011)_2$.

From the previous page in the book it was proven using induction that $J(2^m+l)=2l+1$ for $m\geq0$ and $0\leq l<2^m$. All the author wants to do now is to represent $2^m+l$ and $2l+1$ using binary.

Notice that $$2^m+l=1*2^m+b_{m-1}2^{m-1}+...+b_1*2^1+b_0*2^0=(1b_{m-1}b_{m-2}...b_1b_0)_2$$ and since we know $0\leq l<2^m$ it must be the case that $l=(0b_{m-1}b_{m-2}...b_1b_0)_2$ (remember these are the same $b_i$'s in the representation for $2^m+l$ above). It should be quite easy to see why $2l=(b_{m-1}b_{m-2}...b_1b_00)_2$, i.e. $$2(0*2^{m}+b_{m-1}*2^{m-1}+b_{m-2}*2^{m-2}+...+b_1*2^1+b_0*2^0)$$all powers of 2 simply increase by 1. The last two equations $2l+1$ and $J(n)$ I leave to you.