The repertoire method is never really explained in the book, or anywhere else I could find on the Internet. There are a couple of posts on this subject, so I though I should add mine.

The repertoire method is really a tool to help with the intuitive step of figuring out a closed formula for a recurrence equation. It does so by breaking the original problem into smaller parts, with the hope they might be easier to solve.

### Why it works

Let’s assume we have a system of recurrence equations with parameters, so that the unknown function can be expressed as a linear combination of other (unknown) functions where the coefficients are the parameters:

We can consider $g$ as a specific point in a $m$-dimensional function space (determined by both the recurrence equations, and the parameters), and because $g$ is a linear combination, we can try to find $m$ base functions (hopefully known or easy to compute) $f_k(n) = \sum_{i=1}^m A_i(n)\alpha_{i_k}$ with $1 \le k \le m$, expressed in terms of $m$ linearly independent vectors $(\alpha_{1_k},\cdots,\alpha_{m_k})$.

In other words, if we can find $m$ linearly independent parameter vectors such that, for each, we have a known solution $f_k(n)$, then we can express the function $g$ as a linear combination of $f_k(n)$ for any parameters (because the $m$ $f_k(n)$ form a base for the $m$-dimensional function space defined by the recurrence equations).

### How it works

First, we need to check that the recurrence equations accept a solution expressed as

It is enough to plug this definition into the recurrence equations, and make sure the different parameters always remain in different terms.

Then we can either solve $f(n) = \sum_{i=1}^m A_i(n)\alpha_i$ for known $f(n)$, or for known $\alpha_i$ parameters, as long as we end up with $m$ linearly independent parameter vectors (or, as it is equivalent, $m$ linearly independent known functions for specific parameters).

It is important to keep in mind that a solution can be searched from both direction: either set a function and try to solve for the parameters, or set the parameters and solve for the function.

### Homework exercise

Given

We need to check that $g$ can be written as

The base case is trivial. The recurrence case is

so $g$ can be expressed as a linear combination of other functions, with the parameters as the coefficients.

Now, when I tried to solve this problem, I didn’t know I could set the parameters to values that would lead to an easy solution ($\gamma = 0$ turns the problem into an easy to solve generalised radix-based Josephus problem); instead I wasted a lot of time trying to find known functions and solve for the parameters, which is why I have four steps below instead of just two as in the book.

#### $g(n) = n$

As the book suggests, I tried to solve for $g(n) = n$:

#### $g(2^m+l) = 3^m$

As the recurrence equation looks like the generalised radix-based Josephus equation, I tried to solve for $g(2^m+1) = 3^m$:

#### $g(n) = 1$

I tried to solve for $g(n) = 1$, as it seemed useful to solve for a constant (no linear combination of linearly independent non-constant functions can produce a constant function).

#### $\alpha, \beta_1 = 1, \beta_0, \gamma = 0$

This is the step that took me the longest, and when I finally understood I could fix the parameters, I was able to use the radix-based Josephus solution.

The recurrence equations

have as solution $g(2^m + (b_m\cdots b_0)) = 3^m + (b_m\cdots b_0)_3$.

#### Solving for $g(n)$

We have the equations

We have two functions already defined ($A(n)$ and $B_1(n)$), and the other two equations give us the remaining function.

Now we can solve for $g(n)$:

The $\gamma$ term is really $h_3(n) - n$.

The $\beta_0$ term is the same as $h_3(2^m-1-l)$, as can be seen by observing that in base $3$, $3^m$ is $1$ followed by $m$ zeroes, so $3^m-1$ is $m$ twos, and $\frac{3^m-1}{2}$ is $m$ ones, in other words the same representation as the binary representation of $2^m-1$.

Now, the binary representation of $l$ is the same as the representation in base $3$ of $h_3(l)$ (by definition of $h_3$), so the binary representation of $2^m-1-l$ is the same as the representation in base $3$ of $\frac{3^m-1}{2} - h_3(l)$.

With these two observations, it is possible to rewrite $g$ as

which is the book solution.

### Faster solution

It is enough to solve for $\alpha, \beta_0, \beta_1 \ne 0, \gamma = 0$, and to find the parameters for $g(n) = n$. The first gives $A$, $B_0$ and $B_1$ directly by the generalised radix-based Josephus solution, and the second one adds a constraint to solve for $C$ as well.

### Wrapping up

As can be seen above, approaching the problem from both directions (solving for known functions and solving for known parameters) can result in time saved, and simplified expression of the solution.