Concrete Mathematics: Josephus Problem: Odd induction

Question

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.

Answer 1

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.