I am looking into something called the Josephus problem, which seems to be popular, so I am sure there are lots of explanations online, but I want to do the work myself, but I do need a small push to go in the right direction.
I derived the following recursions:
$J(2n) = 2J(n) - 1$
$J(2n+1) = 2J(n) + 1$
and $J(1) = J(2) = 1$ as base cases.
I want to find closed-forms for these equations. I have a few questions:
For problems like these is it considered a good idea to solve even and odd separately? I worry that if I try to combine them, it will involve messy floor operators and make analysis hard.
I tried substitution methods for $n$ even and was flabbergasted to find that the answer was $1$, but then I realized that it assumes $n$ is always even all the way down the chain (when $n$ is a power of $2$), so that approach was not actually helpful. If substitution isn't the right tool here, what other options do I have?
I realize that if I crank out values from the recurrence equations, I'll probably see a pattern and be able to prove a closed-form by induction, but I don't want to do that. I want to assume that the pattern is not obvious so that later on when I do encounter another problem like this, I'll know what to do when guessing and proving by induction doesn't work either.