Concrete Mathematics - The Josephus Problem

Question

I've been going through Concrete Mathematics and have a question on the inductive proof for the Josephus problem.

Recurrent relation:

$J(1) = 1$

$J(2n) = 2J(n) - 1$

$J(2n+1) = 2J(n) + 1$

Closed form hypothesis:

$J(2^m + l) = 2l + 1$, for $m \ge 0$ and $0\le l<2^m$

Inductive Proof (for the even case):

$J(1)=1$

$J(2^m+l)= 2J(2^{m-1}+l/2)-1=2(2l/2+1)-1=2l+1$

How do the authors get from $2J(2^{m-1}+l/2)-1$ to $2(2l/2+1)-1$?

Answer 1

$J(2^m + l) = 2l + 1$ is your hypothesis. You prove it for $n=0$ and $l=0$. Now comes the step. You assume the hypothesis for numbers smaller then m and l.

Then for $n=m-1$ and $k=\frac l2$, you have $J(2^n + k) = 2k + 1=\frac{2k} 2+1$ from the hypothesis. This is induction.