Day 24: CM, Page 11

Day 24: The authors prove the closed form of the Josephus problem by induction. They prove the odd and even cases separately.

Base case: J(1) = J(2^0 + 0) = 2(0) + 1 = 1
Assume: J(2n) = 2(J(n)) - 1 and J(2n + 1) = 2(J(n)) + 1
Inductive Hypothesis Even: J(n/2) = J(2^(m-1) + l/2) = 2l/2 + 1
Inductive Hypothesis Odd: J((n-1)/2) = J(2^(m-1) + (l-1)/2) = 2(l-1)/2 + 1

This a different twist on the normal induction process. Rather than assuming n-1 is true, we are assuming n/2 is true for all even numbers. Then:

And a similar proof for odd numbers:


Together, the two proofs cover all even and odd numbers. Next the authors suggest trying to generalize the problem. There seems to be a relationship in the problem between powers of 2, so let's represent the problem in binary.


That last step follows because J(n) = 2l + 1 and b sub m = 1. This is a pretty interesting result. J(n) can be calculated by doing a one bit cyclic left shift on n. More details from the CM authors tomorrow about this new observation tomorrow.