The repertoire method is an method of finding closed-form of recurrence relations and sum of a series. The method is introduced in Chapter 1 of ConMath but most readers at the first time seem to struggle with it. Through the book, especially Chapter 1 and 2, the repertoire method demonstrates its ability to solve many sums and recurrences. However, I honestly admit that it is quite difficult to apply and fully understand how it works. In this note, I try to figure the way to effectively apply the method for solving recurrences.

Definition

In essence, the main goal of the method is to find coefficients 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 coefficients multiplied by functions of nn Therefore, if we have to find 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 coefficients but they do not mention how they figure out. Regarding this aspect, Sedgewick’s book obtains accessible clarification and systematic examples. Therefore, I use the procedure in Sedgewick’s book as a recipe for the repertoire method:

  1. Relax the recurrence by adding an extra function term.
  2. Substitue known functions into the recurrence to derive identities similar to the recurrence.
  3. Take linear combination of such identities to derive an equation identical to the recurrence.

At the first look, it is quite abstract. However, some examples carried out in the book illustrate how we manipulate the steps. Suppose that we have recurrence an=an1+stuffa_{n} = a_{n-1} + {\text stuff} . First we generalize the identity by replacing stuff{\text stuff} with f(n)f(n), i.e., an=an1+f(n)a_{n} = a_{n-1} + f(n). We easily obtain f(n)=anan1f(n) = a_{n} - a_{n-1}. The next step is to build a table of ingredients in which we can construct f(n)f(n). Finally, we determine coefficients of each component so that they satisfy f(n)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 except understanding purposes. Section 2.5 from Sedgewick’s book summarizes some approaches to finding the closed-form including the repertoire method. Examples in the book are required reading.

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

Examples

Closed-form of sums

We can easily convert sum of a sequence into a linear recurrence. Let begin with the first example which only contains term n3n^3.

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

This sum can be seen as:

a0=0 a_{0} = 0 an=an1+n3 a_{n} = a_{n-1} + n^3

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

ana_n anan1a_n -a_{n-1}
1 0
n 1
n2n^2 2n12n-1
n3n^3 3n23n+13n^2-3n+1
n4n^4 4n36n2+4n14n^3-6n^2+4n-1

How can I fill ana_n? Since we want f(n)f(n) obtains n3n^3 and we observe that f(n)=anan1f(n) = a_n - a_{n-1} depends on the degree of nn in ana_n and hence we come up with some simple sequence, i.e., computing anan1a_n - a_{n-1}. Turn out f(n)f(n) have smaller degree of nn than ana_n exactly 1. f(n)f(n) obtaining n3n^3 means that ana_n has to obtain n4n^4. The simplest form we can come up with is n3=α(4n36n2+4n1)n^3 = \alpha (4n^3-6n^2+4n-1). So α=14\alpha = {1\over 4}, we need to eliminate n2n^2, nn and constants. In the second attempt, we add n3n^3 and n2n^2 into the linear combination:

α(4n36n2+4n1)+β(3n23n+1)+λ(2n1)=n3 \alpha (4n^3-6n^2+4n-1) + \beta(3n^2-3n+1) + \lambda (2n-1) = n^3

{6α+3β=04α3β+2λ=0α+βλ=0 \begin{cases} -6\alpha + 3\beta = 0\newline 4\alpha -3\beta + 2\lambda = 0\newline -\alpha + \beta - \lambda = 0 \end{cases}

The solution is (α,β,λ)=(14,12,14)(\alpha, \beta,\lambda) =({1\over 4}, {1\over 2}, {1\over 4}) and hence an=αn3+βn2+λn=14n2(n+1)2a_n = \alpha n^3 + \beta n^2 + \lambda n = {1\over 4}n^2(n+1)^2. Also, since a0=0a_0 = 0, it is the final solution.

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

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

ana_n anan1a_n-a_{n-1}
(1)nn2(-1)^nn^2 (1)n(2n22n+1)(-1)^n(2n^2-2n+1)
(1)n(-1)^n 2(1)n2(-1)^n
(1)nn(-1)^nn (1)n(2n1)(-1)^n(2n-1)

The solution is Sn=12(1)nn(n+1)S_n = {1\over 2}(-1)^n n(n+1) since we just add the first term and the last term together and then divide by 2, we get f(n)f(n). When I first saw the sum, I could not think any sequences which help me find f(n)f(n). After play which some sequences, I realize that assigning an=f(n)=(1)nn2a_n = f(n) = (-1)^nn^2 actually lets other patterns be discovered.

Linear Recurrences

a0=7 a_0 = 7

an=an1+2n2+7;n>0 a_n = a_{n-1} + 2n^2 + 7 ; n > 0

Based on the table we built in previous examples, we can construct a linear combination for the recurrence:

α(3n23n+1)+β(2n1)+λ1=2n2+7\alpha(3n^2-3n+1) + \beta(2n-1) + \lambda 1 = 2n^2+7

{3α=23α+2β=0αβ+λ=7 \begin{cases} 3\alpha = 2 \newline -3\alpha + 2\beta = 0 \newline \alpha - \beta + \lambda = 7 \end{cases}

The solution is (α,β,λ)=(23,1,223)(\alpha, \beta, \lambda) = ({2\over 3}, 1, {22\over 3}). However, at this time a0=07a_0= 0 \neq 7, we have to add constant 77 to the final form. The closed-form is an=23n3+n2+223n+7a_n = {2\over 3}n^3+n^2+{22\over 3}n+7.

Exercise 1.16 (ConMath)

g(1)=α g(1) = \alpha g(2n+j)=3g(n)+γn+β;j=0,1;n1 g(2n+j) = 3g(n) + \gamma n + \beta ; j = 0, 1 ; n \geq 1

Related Materials

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