I've recently been looking at sites trying to prove the Josephus Problem lately, such as the Wikipedia page, or this cut-the-knot site but I'm confused as to how they came up with these relationships:
f(2j) = 2f(j) - 1, if the number of people is even
f(2j+1) = 2f(j) + 1, if the number of people is odd
Could someone please explain to me how they got these two relationships?
OK, so the problem is this: there are $n$ people in a circle, with positions 1 through n. We are going to start counting with position 1, and execute every second person that is still left standing. That is, we will first execute person in position 2, then 4, etc. and keep going around the circle, executing one, skipping the next, executing the next, skipping the next, etc. So, for example, if $n=5$, we will skip 1, execute 2, skip 3, execute 4, skip 5, execute 1, skip 3 (since 2 is already gone), and execute 5, so 3 is the survivor. But thew question is: for any $n$, who will survive?
OK, so let $f(n)$ be the position number that survives. Now, there are two cases to consider: $n$ is even or $n$ is odd.
If $n$ is even, i.e. $n=2m$ for some $m$, then we execute $2,4,6,...,2m=n$, meaning that once we have gone around the circle once, we are left with $1,3,...n-1$. But, this means there are $m$ people left, and since we start with skipping 1 for our second round, the question of who survives is really just the same question as who survives when we would have started out with just $m$ people, except that in terms of the position number: if the survivor in the 'game' with $m$ people in positions $1,2,...,m$ is in position $f(m)$, then in the game where the $m$ positions are $1,3,5,...2m-1$, the survivor will be in position $2*f(m)-1$ (since 1 corresponds to 1, 2 with 3, 3 with 5, etc). That is: $f(n) = f(2m) = 2*f(m)-1$, so just taking the last part: $f(2m) = 2*f(m)-1$. So that is the first equation.
If $n$ is odd, i.e. $n=2m+1$ for some $m$ then in the first round we execute $2,4,6,...,2m$ ... followed by 1. OK, ate that point we are left with $3,5,...2m+1$, which are $m$ people. So again we can say that it has come down to playing the 'game' with $m$ people, but instead of them being in positions $1,2,...,m$, they are in positions $3,5,...2m+1$. Thus, if $f(m)$ is the survivor with positions $1,2,...,m$, then the survivor with positions $3,5,...2m+1$ will be $2*f(m)+1$ (1 corresponds to 3, 2 with 5, 3 with 7, etc., so: multiply by 2 and add 1). So we get: $f(n)=f(2m+1) = 2*f(m)+1$, and again the last part is the second equation we were looking for: $f(2m+1) = 2*f(m)+1$.
Of course, that still doesn't give us the whole solution, but it gives us two equations from which we can then derive the solution. But you asked about just two equations and how they got to them, so I hope I explained that above.