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.