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


Logically, then, these two are equivalent


Which finally gives us what we want


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:


Then plugging in the closed form:


But then this does not induct:


I am not sure what I am misunderstanding.


1 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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .