Josephus Problem recurrence relation I am going through the Josephus problem and I am not able to understand the recurrence relation.
The solution says that for $2n$ people, the actual number of person in the $2n$-d round can be mapped using
$$J(2n)=2\cdot J(n)-1 \qquad\rm{eq.1}$$
and for 2n+1 people the numbering in the 2nd round can be mapped using
$$J(2n+1) = 2 \times J(n)+ 1 \qquad\rm{eq.2}$$
I understand the R.H.S of these $2$ equations.
In case of $2n$ people, after the first round the actual number of the person at position $1$ is $1 = 2 \times J(1)-1$, actual number of person $2$ is $3 =2 \times J(2)- 1$.
Same goes for the $2n+1$ equation too, actual number of person $1$ after round $1$ is $3 = 2 \times J(1)+ 1$.
What I do not understand is L.H.S, what does $J(2n)$ and $J(2n+1)$ mean here?
Why $2n$ and $2n+1$?
If I substitute '$1$' in eq.1, we get $J(2 \times 1)=2 \times J(1) - 1 \implies J(2)=1$; which is not correct.
What am I missing here?
Also how is it that using these equations I can calculate the position of the person that survives? Since these equations only represent the position of the person.
Thanks
 A: You’ve misunderstood the function $J$. $J(n)$ is the position number of the last survivor when we start with a circle of $n$ people. It is not the number of people left after the first round.
If $n=1$, the last survivor is of course person $1$, so $J(1)=1$. If $n=2$, the last survivor is again person $1$, so $J(2)=1=2J(1)-1$. If $n=4$, the first round kills off persons $2$ and $4$, and the second round kills off person $3$, so person $1$ is yet again the final survivor, and $J(4)=1=2J(2)-1$. If $n=3$, however, the first round kills off person $2$, the second round kills off person $1$, and person $3$ is the last survivor, so $J(3)=3=2J(1)+1$.
You can use the recurrences $J(2n)=2J(n)-1$ and $J(2n+1)=2J(n)+1$ and the initial condition $J(1)=1$ to calculate the final survivor for any $n$ simply by working backwards. If we start with $n=21$, for instance, we have
$$\begin{align*}
J(21)&=J(2\cdot 10+1)\\
&=2J(10)+1\\
&=2J(2\cdot 5)+1\\
&=2\big(2J(5)-1\big)+1\\
&=4J(5)-1\\
&=4J(2\cdot 2+1)-1\\
&=4\big(2J(2)+1\big)-1\\
&=8J(2)+3\\
&=8J(2\cdot 1)+3\\
&=8\big(2J(1)-1\big)+3\\
&=16J(1)-5\\
&=16\cdot 1-5\\
&=11\,.
\end{align*}$$
