Concrete Maths - Josephus Problem
in [Math]
|
Prev: Mental Math generalizations
Next: Goldbach proof as the world's easiest Mathematical Induction proof?#5.28 Correcting Math
From: J Kenneth King on 12 Aug 2010 17:33 I've managed to work my way through the induction proof of the Josephus recurrence problem from Concrete Mathematics (Graham, Knuth, Patashnik). I'm having a problem with a particular deduction made during the discovery of the even case. We get to the part where we assume 2n for the input of J(n) which we can then derive 2J(n) - 1 and get our answer. However, at the end it's stated that one can deduce that J(5 * 2^m) = 2^m+1 + 1... The rest of the explanation of the problem and the subsequent induction proof is quite easy to understand, but I don't see any mention of this "deduction" and its importance anywhere else. I feel like I'm still missing something important. Any ideas? |