Concrete Mathematics - The Josephus Problem

$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{2l} 2+1$ from the hypothesis. This is induction.

For the purposes of our induction, we assume that our hypothesis is true. A reminder of our hypothesis:

$J(2^m + l) = 2l + 1$

If that's true then:

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

And if that's true then:

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

Which is, of course:

$2l + 1$

The even part of our induction is complete.