# Concrete Mathematics: Josephus Problem: Odd induction

I am trying to work through the odd induction case of the closed form solution to the Josephus problem. To start with a quick review of the even case - I'm being quite verbose though to help frame the question and also to potentially highlight any mistakes in my understanding that just happen to work in the even case.

### Quick review of even case

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

Closed form to prove: $$J(2^m+l)=2l+1$$

First we express it in terms of the recurrence

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

Logically, then, these two are equivalent

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

Which finally gives us what we want

$$2(\frac{2l}{2}+1)-1=2(l+1)-1=2l+2-1=2l+1$$

### Odd case

Odd recurrence: $$J(2n+1)=2J(n)+1$$

I am trying to apply the closed form in the same way. First in terms of the odd recurrence:

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

Then plugging in the closed form:

$$2(2\frac{l}{2}+1)+1$$

But then this does not induct:

$$2(\frac{l}{2}+1)+1=2(l+1)+1=2l+3$$

I am not sure what I am misunderstanding.

You’re not applying the recurrence for the odd case correctly. Suppose that $$2n+1=2^m+\ell$$, where $$0\le\ell<2^m$$. The recurrence is $$J(2n+1)=2J(n)+1$$, and $$n$$ here is $$\frac12(2^m+\ell-1)$$, so
\begin{align*} J(2^m+\ell)&=2J\left(2^{m-1}+\frac{\ell-1}2\right)+1\\ &=2\left(\frac{2(\ell-1)}2+1\right)+1\\ &=2\ell+1\;, \end{align*}