Day 26: CM, Page 13

Day 26: The Josephus problem continued. The authors generalize the Josephus problem even further. They ask the question: how would we find a closed form for the recurrence if the pattern had been more complex? What if the coefficients on the recurrence were something besides -1 and +1? To generalize the recurrence:


By expanding the recurrence, we can build a table of values for f(n):


If we write f(n) as:
Then, it appears that:
More on these equations tomorrow.