Concrete Mathematics - The Josephus Problem

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$?

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

Solution 2:

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.

Solution 3:

Base case.
Obviously $J(1) = 1$.
Inductive step.
Assume $J(\frac{n}{2}) = J(2^{m-1} + \frac{l}{2}) = 2 \cdot \frac{l}{2} + 1.$
We have $J(n) = J(2 \cdot \frac{n}{2}) = J(2^m + l) \stackrel{(1.8)}{=} 2J(\frac{n}{2}) - 1 = 2l + 1.$
Proofed.