# Clarification regarding the Josephus problem in Concrete Mathematics (Knuth, et al)

In page 9 of Concrete Mathematics, regarding the Josephus Problem, they state that "each person's number has been doubled then decreased by 1".

$J(2n) = 2J(n) - 1$, for $n \ge 1$

I don't quite understand where the subtraction of 1 comes in.

This also goes for the odd problem where the formula is given as:

$J(2n+1) = 2J(n) + 1$, for $n \ge 1$

I know I'm missing an obvious piece of logic here but I haven't figured it out so far...

For the even case, the reason for the decrease is that instead of having $n$ numbers as:

$\qquad 1,2,3, \ldots n\qquad$ we have $\qquad 1,3,5, \ldots 2n-1$

So the $i^{th}$ number is $2i - 1$ now. So whatever $J\left(n\right)$ is we need to double it and subtract $1$ to get the correct result.

Similarly for the odd case, instead of the $n$ numbers as:

$\qquad 1,2,3, \ldots n\qquad$ we have $\qquad 3,5,7, \ldots 2n+1$

So the $i^{th}$ number is $2i + 1$ now.

• Right, so it's got to do with the positioning of the numbers after every second number is removed. But I don't understand the leap of logic from determining the new positioning with this equation to actually solving for the number that remains... – momo Aug 2 '14 at 12:05
• We initially had (for the even case) $2n$ numbers, now we have $n$ numbers. So it means if we can evaluate $J(n)$ then we can evaluate $J(2n)$. Eg. we know $J(1)=1$ so our eqn gives us $J(2)=2*J(1)-1=1, J(4)=2J(2)-1=1$, and so on. What's really happening here for $J(4)$: start with "1,2,3,4". After one cycle we have: "1,3". We know $J(2)=1$, which means if we have 2 numbers, the 1st will be the survivor. It doesn't matter if those 2 numbers are "1,2" or "1,3" or "1698, 543" - the number in position 1 survives. So for "1,3" we know 1 is the answer. I hope I have understood you correctly. :-) – Mick A Aug 2 '14 at 12:52
• Ah yes, your comment + a little reading on the wiki cleared it up for me. I forgot that this is solved with recursion. – momo Aug 3 '14 at 8:59