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.
Best Answer
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*}$$
as desired.