The repertoire method

The repertoire method is an approach to find a closed-form for recurrence relations and sum of series. The method is introduced in Chapter 1 of ConMath but most readers at the first time struggled with it. Through the book, especially in 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 do not 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 main is to find coefficients for a linear combinations of a set of recurrences. This method works very well on linear recurrences. 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 can 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 formal 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 time, it is quite abstract. However, some examples carried out in the book illustrate how we can manipulate the steps. Suppose that we have a recurrence $a_{n} = a_{n-1} + {\text stuff} $. First we generalize the identity by replacing ${\text stuff}$ by $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 in which we can construct $f(n)$. Finally, we determine coefficients of each component so that it satisfies $f(n)$ and the initial value 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 book for practicing the method except understanding purposes. Section 2.5 from Sedgewick’s book summarizes some approaches for find 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 a sum of a sequence into a linear recurrence. Let begin with the fist example which only contains a term $n^3$.

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

This sum can be seen as: $ a_{0} = 0$ $ a_{n} = a_{n-1} + n^3$

Next we have to 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$ $2n-1$
$n^3$ $3n^2-3n+1$
$n^4$ $4n^3-6n^2+4n-1$

How do I can fill these value of $a_n$? Since we want $f(n)$ obtains $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 sequence, compute $a_n - a_{n-1}$. Turn out $f(n)$ have smaller degree of $n$ than $a_n$ 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 = \alpha (4n^3-6n^2+4n-1)$. So $\alpha = {1\over 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: $$ \alpha (4n^3-6n^2+4n-1) + \beta(3n^2-3n+1) + \lambda (2n-1) = n^3 $$

$$ \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 $(\alpha, \beta,\lambda) =({1\over 4}, {1\over 2}, {1\over 4}) $ and hence $a_n = \alpha n^3 + \beta n^2 + \lambda n = {1\over 4}n^2(n+1)^2$. Also, since $a_0 = 0$, it is the final solution.

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

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

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

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

Linear Recurrences

$ a_0 = 7 $

$ 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:

$\alpha(3n^2-3n+1) + \beta(2n-1) + \lambda 1 = 2n^2+7$

$$ \begin{cases} 3\alpha = 2 \newline -3\alpha + 2\beta = 0 \newline \alpha - \beta + \lambda = 7 \end{cases} $$

The solution is $(\alpha, \beta, \lambda) = ({2\over 3}, 1, {22\over 3})$. However, at this time $a_0= 0 \neq 7$, we have to add constant $7$ to the final form. The closed-form is $a_n = {2\over 3}n^3+n^2+{22\over 3}n+7$.

Exercise 1.16 (ConMath)

$$ g(1) = \alpha $$ $$ 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:

  • 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.
comments powered by Disqus