The repertoire method

by Le Tan Dang Khoa, Dec 26, 2017

The repertoire method is a method of ﬁnding closed-form solutions to recurrence relations and sums of a series. The method is introduced in Chapter 1 of ConMath but most readers at ﬁrst seem to struggle with it. Throughout the book, especially Chapters 1 and 2, the repertoire method demonstrates its ability to solve many sums and recurrences. However, I honestly admit that it is quite difﬁcult to apply and fully understand how it works. In this note, I try to ﬁgure the way to effectively apply the method for solving recurrences.

Deﬁnition

In essence, the main goal of the method is to ﬁnd coefﬁcients for a linear combination of a set of recurrences. This method works very well on linear recurrences, in the sense that the solutions can be expressed as a sum of coefﬁcients multiplied by functions of $n$ . Therefore, if we have to ﬁnd a closed-form of a linear recurrence, this is worth trying.

The method is not described clearly in ConMath because the authors always come up with a set of recurrences and get their coefﬁcients but they do not mention how they ﬁgure it out. Regarding this aspect, Sedgewick’s book provides accessible clariﬁcation and systematic examples. Therefore, I use the procedure in Sedgewick’s book as a recipe for the repertoire method:

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.

At ﬁrst glance, it is quite abstract. However, some examples carried out in the book illustrate how we manipulate the steps. Suppose that we have recurrence $a_{n} = a_{n - 1} + stuff$ . First we generalize the identity by replacing $stuff$ with $f (n)$ , i.e., $a_{n} = a_{n - 1} + f (n)$ . We easily obtain $f (n) = a_{n} - a_{n - 1}$ . The next step is to build a table of ingredients from which we can construct $f (n)$ . Finally, we determine coefﬁcients of each component so that they satisfy $f (n)$ and the basis of the recurrence.

For more details and explanations, I strongly recommend reading Markus Scheuer’s answer. Of course, ConMath (Chapter 1, 2, 6) is a good material for practicing the method for understanding purposes. Section 2.5 from Sedgewick’s book summarizes some approaches to ﬁnding the closed-form, including the repertoire method. Examples in the book are recommended reading.

The best way to fully understand the method is to work through examples.

Examples

Closed-form of sums

We can easily convert the sum of a sequence into a linear recurrence. Let’s begin with the ﬁrst example, which only contains the term $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 can I ﬁll $a_{n}$ ? Since we want $f (n)$ to obtain $n^{3}$ and we observe that $f (n) = a_{n} - a_{n - 1}$ depends on the degree of $n$ in $a_{n}$ and hence we come up with some simple sequences, i.e., computing $a_{n} - a_{n - 1}$ . Turns out $f (n)$ has a smaller degree of $n$ than $a_{n}$ by exactly 1. $f (n)$ obtaining $n^{3}$ means that $a_{n}$ has to obtain $n^{4}$ . The simplest form we can come up with is $n^{3} = α (4 n^{3} - 6 n^{2} + 4 n - 1)$ . So $α = \frac{1}{4}$ , we need to eliminate $n^{2}$ , $n$ , and constants. In the second attempt, we add $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 $(\alpha, \beta, \lambda) =({1\over 4}, {1\over 2}, {1\over 4}) $ and hence $a_{n} = α n^{3} + β n^{2} + λ n = \frac{1}{4} n^{2} (n + 1)^{2}$ . Also, since $a_{0} = 0$ , it is the ﬁnal solution.

Let’s try another example, this time we use an exercise in ConMath:

S_{n} = \sum_{k = 0}^{k} (- 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)$ since we just add the ﬁrst term and the last term together and then divide by 2, we get $f (n)$ . When I ﬁrst saw the sum, I could not think of any sequences which help me ﬁnd $f (n)$ . After playing with some sequences, I realized that assigning $a_{n} = f (n) = (- 1)^{n} n^{2}$ actually lets other patterns be discovered.

Linear Recurrences

a_{0} = 7

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

Based on the table we built in previous examples, we can construct a linear combination for the 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}

The solution is $(α, β, λ) = (\frac{2}{3}, 1, \frac{22}{3})$ . However, at this time $a_{0} = 0 \neq 7$ , we have to add the constant $7$ to the ﬁnal form. The closed-form is $a_{n} = \frac{2}{3} n^{3} + n^{2} + \frac{22}{3} n + 7$ .

Exercise 1.16 (ConMath)

g (1) = α

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

After hours searching on the Internet, I found some useful links which actually help me understand the method:

Wakatta’s post
Math stackexchange answer: this one is damn good.
Pindancing’s post
Sedgewick, Robert, and Philippe Flajolet. An introduction to the analysis of algorithms. Pearson Education India, 1996. [IMO, the explanation in this book is much better than in ConMath.]
Graham, Ronald L., et al. “Concrete mathematics: a foundation for computer science.” Computers in Physics 3.5 (1989): 106 – 107.

The reper­toire method