i have studied the Josephus problem from the concrete mathematics book.I have understand all related calculations discussed on that book.However i have some difficulties regarding to recurrence relations of Josephus problem.
J(1) = 1 ;
J(2n) = 2J(n) − 1 , for Even number
J(2n + 1) = 2J(n) + 1 , for Odd number
I did several trials with many sample numbers(both even & odd) and this 2 recurrence relations holds perfect every time.I also understand it closed forms. But however, my mind gets lost whenever i try to rediscover these recurrence relations without seeing the solutions. So my curiosity on knowing:
Why to start with 2n instead of n ? (i got this one now)
What questions i should ask my self to predict these recurrence relations(J(2n) = 2J(n) − 1 and J(2n + 1) = 2J(n) + 1) intuitively?
again don't misunderstand me. i already did all calculations and understand maths in behind it.So no need to demonstrate any even odd examples.But i am missing the intuitive picture in my mind.Thats why these recurrences became memorization to me.
please reply & enlighten me with your creative explanation. :)