Day 27: CM, Page 14

Day 27: The authors introduce the repertoire method by an example with the Josephus problem. Recall from yesterday that we believe:

A(n) = 2^m
B(n) = 2^m - 1 - l
C(n) = l

How can we prove this? One way is to find a series of equalities based on specific data points, then to solve those equalities. No hints yet on how to find the specific data points to form the equalities. The authors make a few clever observations to find their data points. We'll assume that f(n) = A(n)(alpha) + B(n)(beta) + C(n)(gamma).

What happens in the case where alpha=1, beta=0, gamma=0? We have f(n) = A(n) or:

A(1) = 1
A(2n) = 2A(n)
A(2n+1) = 2A(n)

We want to show that A(n) = 2^m. This follows from the equations above by induction. A(1) = 1 since A(1) = alpha. Assume A(n/2) = 2^(m-1). Then:

A(n) = A(2^m + l) = 2A((2^m + l)/2) = 2(2^(m-1)) = 2^m.

Next we want some other interesting data points. What are some other values for alpha, beta, and gamma that make it easy to solve our recurrences? How about f(n) = 1:

1 = alpha
1 = 2*1 + beta
1 = 2*1 + gamma

For this to be true, alpha=1, beta=-1, and gamma=-1. Plugging that back in, we get:

A(n) - B(n) - C(n) = f(n) = 1

What happens if f(n) = n? In that case:

1 = alpha
2n = 2n + beta
2n+1 = 2n + gamma

So in this case, alpha=1, beta=0, and gamma=1. Plugging that back in, we get:

A(n) + C(n) = n

Now that we have three inequalities, we can solve them. From our first observation, we directly have A(n) = 2^m

That gives us:
A(n) + C(n) = n
C(n) = n - A(n) = 2^m - l - 2^m = l

Which matches what we expect. And finally:

A(n) - B(n) - C(n) = 1
B(n) = A(n) - C(n) - 1
B(n) = 2^m - l - 1

And that matches all our observations for A(n), B(n), and C(n) of:

A(n) = 2^m
B(n) = 2^m - l - 1
C(n) = l

This is an illustration of the repertoire method. There are still some questions to work out - how do we choose the right specific data points to use for our equalities? I suspect we'll return to this in the exercises. More on the Josephus problem tomorrow.