The repertoire method

by Le Tan Dang Khoa, Dec 26, 2017

The repertoire method offers an elegant technique for ﬁnding closed-form solutions to recurrence relations and series sums. Introduced in Chapter 1 of Concrete Mathematics (Graham et al. 1989), it tends to puzzle newcomers at ﬁrst glance. Yet throughout the book—especially Chapters 1 and 2—this method proves remarkably powerful for tackling diverse sums and recurrences. I’ll be honest: the technique takes some effort to master. In this note, I attempt to demystify the repertoire method and show how to apply it effectively.

Deﬁnition

At its core, the repertoire method seeks coefﬁcients for a linear combination of related recurrences. It shines brightest with linear recurrences—those whose solutions can be expressed as sums of coefﬁcients multiplied by functions of $n$ . If you’re hunting for a closed-form expression of a linear recurrence, this technique deserves a spot in your toolkit.

Concrete Mathematics doesn’t spell out the method explicitly—the authors conjure up recurrence sets and extract coefﬁcients almost magically, leaving readers wondering how they arrived at them. Fortunately, Sedgewick’s Analysis of Algorithms (Sedgewick and Flajolet 1996) offers clearer guidance with systematic examples. I’ve distilled the approach from (Sedgewick and Flajolet 1996) into a three-step recipe:

Relax the recurrence by adding an extra function term.
Substitute known functions into the recurrence to derive identities similar to the recurrence.
Take linear combinations of such identities to derive an equation identical to the recurrence.

Admittedly abstract at ﬁrst glance! Let’s ground it with an example. Consider a recurrence of the form $a_{n} = a_{n - 1} + stuff$ . We generalize by replacing $stuff$ with an arbitrary function $f (n)$ , giving us $a_{n} = a_{n - 1} + f (n)$ . A quick rearrangement yields $f (n) = a_{n} - a_{n - 1}$ . From here, we build a table of “ingredients”—candidate sequences from which we can construct $f (n)$ . The ﬁnal step determines the coefﬁcients for each ingredient that together satisfy both $f (n)$ and the recurrence’s base case.

For deeper insight, I highly recommend Markus Scheuer’s excellent answer on Math StackExchange. For practice, Concrete Mathematics (Graham et al. 1989) (Chapters 1, 2, and 6) provides a wealth of exercises that build intuition. Additionally, Section 2.5 of (Sedgewick and Flajolet 1996) surveys various closed-form techniques, with the repertoire method among them—the worked examples there are particularly instructive.

Nothing beats working through examples to truly internalize this technique.

Examples

Closed-form of sums

We can readily convert a series sum into a linear recurrence. Let’s begin with a simple example involving $n^{3}$ .

S_{n} = \sum_{k = 0}^{n} k^{3}

This sum can be seen as:

a_{0} = 0

a_{n} = a_{n - 1} + n^{3}

Next, we build a table of $a_{n}$ and $a_{n} - a_{n - 1}$ .

$a_{n}$	$a_{n} - a_{n - 1}$
1	0
n	1
$n^{2}$	$2 n - 1$
$n^{3}$	$3 n^{2} - 3 n + 1$
$n^{4}$	$4 n^{3} - 6 n^{2} + 4 n - 1$

How do we populate the $a_{n}$ column? Since we want $f (n) = n^{3}$ and we notice that $f (n) = a_{n} - a_{n - 1}$ depends on the degree of $n$ in $a_{n}$ , we start with simple power sequences and compute their differences. Observe that $f (n)$ has degree exactly one less than $a_{n}$ . To get $f (n) = n^{3}$ , we’ll need $a_{n}$ to include $n^{4}$ . Starting simply, we try $n^{3} = α (4 n^{3} - 6 n^{2} + 4 n - 1)$ . Setting $α = \frac{1}{4}$ handles the leading term, but leaves us with residual $n^{2}$ , $n$ , and constant terms to eliminate. In our second attempt, we incorporate $n^{3}$ and $n^{2}$ into the linear combination:

α (4 n^{3} - 6 n^{2} + 4 n - 1) + β (3 n^{2} - 3 n + 1) + λ (2 n - 1) = n^{3}

{\begin{cases} - 6 α + 3 β = 0 \\ 4 α - 3 β + 2 λ = 0 \\ - α + β - λ = 0 \end{cases}

The solution is $(α, β, λ) = (\frac{1}{4}, \frac{1}{2}, \frac{1}{4})$ , yielding $a_{n} = α n^{4} + β n^{3} + λ n^{2} = \frac{1}{4} n^{2} (n + 1)^{2}$ . Since $a_{0} = 0$ matches our base case, this is our ﬁnal answer.

Let’s tackle another example—this time an exercise from Concrete Mathematics (Graham et al. 1989):

S_{n} = \sum_{k = 0}^{n} (- 1)^{k} k^{2}

$a_{n}$	$a_{n} - a_{n - 1}$
$(- 1)^{n} n^{2}$	$(- 1)^{n} (2 n^{2} - 2 n + 1)$
$(- 1)^{n}$	$2 (- 1)^{n}$
$(- 1)^{n} n$	$(- 1)^{n} (2 n - 1)$

The solution is $S_{n} = \frac{1}{2} (- 1)^{n} n (n + 1)$ —simply add the ﬁrst and last rows together, then divide by 2 to obtain $f (n)$ . I confess that when I ﬁrst encountered this sum, no obvious candidate sequences came to mind. After some experimentation, I discovered that setting $a_{n} = f (n) = (- 1)^{n} n^{2}$ reveals the underlying patterns quite naturally.

Linear Recurrences

a_{0} = 7

a_{n} = a_{n - 1} + 2 n^{2} + 7 n > 0

Drawing from the table we built earlier, we can construct a linear combination for this recurrence:

α (3 n^{2} - 3 n + 1) + β (2 n - 1) + λ 1 = 2 n^{2} + 7

{\begin{cases} 3 α = 2 \\ - 3 α + 2 β = 0 \\ α - β + λ = 7 \end{cases}

Solving yields $(α, β, λ) = (\frac{2}{3}, 1, \frac{22}{3})$ . However, our formula currently gives $a_{0} = 0 \neq 7$ , so we must add a constant term to satisfy the initial condition. The closed-form solution is $a_{n} = \frac{2}{3} n^{3} + n^{2} + \frac{22}{3} n + 7$ .

Exercise 1.16 (Graham et al. 1989)

g (1) = α

g (2 n + j) = 3 g (n) + γ n + β j = 0, 1; n \geq 1

Helpful Resources

After extensive searching, I’ve collected some resources that genuinely helped me grasp the method:

Wakatta’s post
Math StackExchange answer—this one is particularly illuminating
Pindancing’s post

References

Graham, Ronald L., Donald E. Knuth, and Oren Patashnik. 1989. Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley.
Sedgewick, Robert, and Philippe Flajolet. 1996. An Introduction to the Analysis of Algorithms. Pearson Education India.

The reper­toire method