Mathematical explanation for the Repertoire Method

There are a few questions already about this method, which has stumped me for a long while. The process is explained, for instance, here: Repertoire Method Clarification Required ( Concrete Mathematics )

What I absolutely don't get is: What's the meaning of plugging in simple functions (which are not solutions) in the recurrence and how would that help finding what the right solution really is?

As I understand it, we have a function determined by a recurrence relation and we want to find a closed formula for it. The recurrence being linear, we assume this closed form is a linear combination of 3 other functions, with coefficients $\alpha, \beta$ and $ \gamma$.

The first method suggested in the book is clear to me: set simple values for the constants, since the function will be the same for all of them, and try to guess A, B and C and prove it by induction. What I don't get is the "dual" repertoire method.

$f$ could be anything, but it's something fixed, so I don't see any meaning in this process of plugging in $f(n) = 1$. $f$ clearly is not 1. What is going on?

I expect everything coming down to seeing a vector space / module in two different ways and then somehow picking some basis vectors from each. However, I can't work out the right abstraction.

I'd like to ask for a very explicit top down explanation of this repertoire method, if possible with linear algebra vocabulary.

Solution 1:

Note: At first I'll try to describe some key ideas of the repertoire method using a (very) simple example. This should give you some basic information about this method. But to get a good impression what's really going on, we will also look at a considerably more complex example.

Repertoire method (some basics)

This method is based upon two essential ingredients. The first one is the possibility to build linear combinations of already known recurrences.

Let's assume we have a recurrence for $x_n$ \begin{align*} x_0&=a_0\\ x_n&=a_n+x_{n-1},\quad n>0 \end{align*} and we have another recurrence for $y_n$ \begin{align*} y_0&=b_0\\ y_n&=b_n+y_{n-1},\quad n>0 \end{align*} Then provided these recurrences are known, we also know by linearity that an equation with additive term $$\alpha a_n+\beta b_n$$ will have the solution $$\alpha x_n + \beta y_n$$

To make it more concrete, let $a_n=3$ and $b_n=5n^2+1$. Assuming we know the solutions $x_n$ and $y_n$ of the recurrences \begin{align*} x_0&=3&y_0&=1\\ x_n&=3+x_{n-1},\quad n>0&y_n&=5n^2+1+y_{n-1},\quad n>0 \end{align*}

then we also know by linearity that the solution of the recurrence \begin{align*} z_0&=7\\ z_n&=2n^2+7+z_{n-1} \end{align*} is

\begin{align*} z_n=\frac{11}{5}x_n+\frac{2}{5}y_n \end{align*}

We observe that in this case we have a repertoire of two solutions $x_n$ and $y_n$ which we can linearly combine in order to find the wanted solution $z_n$.

BUT: We typically start with a recurrence $z_n$ without having a repertoire of proper candidates. And this will be the second ingredient. We have to build a repertoire.

The second ingredient is building a repertoire which can be used for linear combinations. Let's assume we start with a recurrence \begin{align*} z_0&=7\\ z_n&=2n^2+7+z_{n-1},\quad n>0\tag{1} \end{align*} So, if we try to solve this recurrence by the method of repertoire, we first generalise the recurrence and consider instead \begin{align*} \mathcal{Z}_0&=a_0\\ \mathcal{Z}_n&=a_n+\mathcal{Z}_{n-1},\quad n>0 \end{align*} Now it's time for some creative ideas which is typically the most challenging phase when using this method. We want to find a repertoire consisting of two members. One of them with $a_n=const.$ and the other with $a_n=$ square of $n$. In order to do so we have to guess some proper candidates for $\mathcal{Z}_n$ which provides us with the wanted $a_n$.

So let's guess a first candidate. This is not too hard (in this case) since setting $\mathcal{Z}_n=n$ gives \begin{align*} a_0&=0\\ n&=a_n+n-1\quad n>0 \end{align*} and we find: $a_0=0$ and $a_n=1,n>0$.

We get the first candidate, let's say $x_n$ with

\begin{align*} x_0&=0\\ x_n&=1+x_{n-1},\quad n>0\tag{2} \end{align*}

We can similarly find a proper second candidate which provides us with $a_n=$ square of $n$ by observing that typically the sum of $k-th$ powers of natural numbers is something with a $(k+1)$-th power. So we guess $\mathcal{Z}_n=n^3$ which gives \begin{align*} a_0&=0\\ n^3&=a_n+(n-1)^3\quad n>0 \end{align*} and we find $a_0=0$ and $a_n=3n^2-3n+1,n>0$.

We get the second candiate, let's say $y_n$ with

\begin{align*} y_0&=0\\ y_n&=3n^2-3n+1+y_{n-1},\quad n>0\tag{3} \end{align*}

We observe that $y_n$ also contains a linear term in $n$ which is not wanted, since we need according to (1) $a_n=n^2+7$. So we extend our repertoire by introducing a third member which provides us with $a_n=$ linear term in $n$. Then we should be able to eliminate the linear term in $n$ by a proper linear combination of the three members. We guess $\mathcal{Z}_n=n^2$ which gives \begin{align*} a_0&=0\\ n^2&=a_n+(n-1)^2\quad n>0 \end{align*} and we find $a_0=0$ and $a_n=2n-1,n>0$.

So we get the third candiate, let's say $u_n$ with

\begin{align*} u_0&=0\\ u_n&=2n-1+u_{n-1},\quad n>0\tag{4} \end{align*}

Let's have a look at the repertoire:

Overview of the three candidates

\begin{array}{rlcr} \mathcal{Z}_n&&a_n&\\ \hline\\ x_n=&n\qquad&1&\qquad\qquad\text{acc. to }(2)\\ y_n=&n^3\qquad&3n^2-3n+1&\qquad\qquad\text{acc. to }(3)\\ u_n=&n^2\qquad&2n-1&\qquad\qquad\text{acc. to }(4)\\ \end{array}

We observe when using an appropriate linear combination \begin{align*} a_n&=2n^2+7\\ &=\frac{2}{3}\left(3n^2-3n+1\right)+\left(2n-1\right)+\frac{22}{3} \end{align*} and we conclude \begin{align*} z_n&=\frac{22}{3}x_n+\frac{2}{3}y_n+u_n+c_0\\ &=\frac{1}{3}n\left(2n^2+3n+22\right)+c_0 \end{align*}

Observe, that we have to determine a constant $c_0$ since we also have to properly respect the initial condition $z_0=7$. We do so by setting $c_0=7$ and so we finally get: $$z_n=\frac{1}{3}n\left(2n^2+3n+22\right)+7,\quad n\geq 0$$

Let's summarise

Summary of the method by Repertoire

In order to solve a recurrence of the form \begin{align*} x_n=f(n)+g(x_{n-1},x_{n-2},\ldots,x_0)\tag{5} \end{align*}

• we identify building blocks $f_1(n),\ldots,f_k(n)$ of $f(n)$, so that they can be linearly combined in order to form $f(n)$

\begin{align*} f(n)=\lambda_1 f_1(n)+\ldots+\lambda_k f_k(n) \end{align*}

• then we consider the generalised representation of (5) by substituting $f(n)$ with $a_n$. \begin{align*} \mathcal{Z}_n=a_n+g(\mathcal{Z}_{n-1},\mathcal{Z}_{n-2},\ldots,\mathcal{Z}_0) \end{align*}

• and solve the simpler recurrences \begin{align*} x_n^{(l)}=f_l(n)+g(x_{n-1},x_{n-2},\ldots,x_0)\quad 1 \leq l \leq k \end{align*} by proper guessing of $x_n^{(l)}$ in order to get $f_l(n)$.

• The solutions $x_n^{(l)}$ with $1\leq l \leq k$ form the repertoire of the method in order to solve $x_n$.

• Determine the linear combination $$f(n)=\lambda_1 f_1(n)+\ldots+\lambda_k f_k(n)$$

• and deduce the solution

$$x_n=\lambda_1 x_n^{(1)}+\ldots+\lambda_k x_n^{(k)}+c_0$$

• Finally determine $c_0$ according to initial conditions

Note: There may be more than one initial condition which are to determine

Note: It may be necessary to extend the repertoire in order to remove unwanted terms which additionally occur during the calculation of the $x_n^{(l)}$.

What follows is no longer a core part of the answer. But if you are curious ... :-)

Note: You may object that the example above uses quite a heavy machinery for a simple recurrence. But this was only for demonstration.

A real life application is presented by D.E.Knuth and D.H.Greene in their Mathematics for the Analysis of Algorithms section 2.1.2.2. Albeit this example is somewhat lengthy, I can't resist to present at least the essential steps, since it's instructive to see the method in action.

Real life application of method by Repertoire: from D.E.Knuth and D.H.Greene

The sorting algorithm median-of-three quicksort leads to the following recurrence.

\begin{align*} x_n=n+1+\frac{1}{\binom{n}{3}}\sum_{1\leq k \leq n}(k-1)(n-k)\left(x_{k-1}+x_{n-k}\right) \end{align*}

At first we observe that the sum is symmetric and we replace the additive term $n+1$ by $a_n$ in preparation for the repertoire approach:

\begin{align*} x_n=a_n+\frac{2}{\binom{n}{3}}\sum_{1< k <n}(k-1)(n-k)x_{k-1} \end{align*}

First step: Create a Repertoire

We choose $x_n$ equal to the falling factorial $(n-1)^{\underline{s}}=(n-1)(n-2)\cdot\ldots\cdot(n-s)$

$$x_n=(n-1)^{\underline{s}}$$

and get

\begin{align*} (n-1)^{\underline{s}}&=a_n+\frac{12}{n^{\underline{3}}}\sum_{1< k <n}(n-k)(k-1)^{\underline{s+1}}\\ &=\ldots\\ &=a_n+\frac{12(s+1)!}{n^{\underline{3}}}\binom{n}{s+3} \end{align*}

This yields \begin{align*} a_n=(n-1)^{\underline{s}}-\frac{12}{(s+2)(s+3)}(n-3)^{\underline{s}} \end{align*} which is a family of solutions for the repertoire parametrised with $s$.

We observe:

\begin{array}{ccc} &x_n&a_n\\ \hline\\ s=0\qquad&1&\qquad-1\\ s=1\qquad&(n-1)&\qquad2\\ s=2\qquad&(n-1)(n-2)&\qquad\frac{1}{5}\left(2n^2+6n-26\right) \end{array}

Attention: Regrettably this family is inadequate; it lacks a member with linear $a_n$. You might want to read section 2.1.2.2 which clarifies why this lack is not surprising (:-))! But we have at least with $s=0$ a candidate for a constant amount.

Second step: Extend the repertoire

Since these types of algorithms are of order $O(n \log n)$ we introduce the Harmonic numbers $H_n=\sum_{k=1}^n\frac{1}{k}$ which contributes $O(\log n)$ and consider a new family $$x_n=(n-1)^{\underline{t}}H_n$$

Solving for $a_n$ yields

\begin{align*} (n-1)^{\underline{t}}H_n&=a_n+\frac{12}{n^{\underline{3}}}\sum_{1< k <n}(n-k)(k-1)^{\underline{t+1}}H_{k-1}\\ &=\ldots\\ &=a_n+\frac{12}{n^{\underline{3}}}\left(\frac{n^{\underline{t+3}}}{t+2}\left(H_{n-1}-\frac{1}{t+2}\right)\right.\\ &\qquad\qquad-\left.\frac{n^{\underline{t+3}}}{t+3}\left(H_n-\frac{1}{t+3}\right)+\frac{(n-1)^{\underline{t+2}}}{t+2}\right) \end{align*}

The calculation above were done using the identity:

$$\sum_{k=1}^{n}\binom{k}{m}H_k=\binom{n+1}{m+1}\left(H_{n+1}-\frac{1}{m+1}\right)$$

Some simplifications lead to \begin{align*} a_n=H_n\left((n-1)^{\underline{t}}-\frac{12}{(t+2)(t+3)}(n-3)^{\underline{t}}\right)+\frac{12(2t+5)}{(t+2)^2(t+3)^2}(n-3)^{\underline{t}} \end{align*}

(... The following text is nearly verbatim from the book ...)

Now when examining the small members of the family of solutions we discover a fortunate alignment:

\begin{array}{ccc} &x_n&a_n\\ \hline\\ t=0\qquad&H_n&\qquad-H_n+\frac{5}{3}\\ t=1\qquad&(n-1)H_n&\qquad2H_n+\frac{7}{12}(n-3)\\ \end{array}

The smallest two solutions for $a_n$ both have leading term $H_n$. By an appropriate linear combination we can eliminate $H_n$ and obtain an $a_n$ that grows as order $n$:

$$x_n=(n+1)H_n\qquad\longleftrightarrow\qquad a_n=\frac{7n+19}{12}$$

The $s=0$ solution from the first family is used to adjust the constant term, enabling us to reconstruct the $a_n$ given in the original problem:

\begin{align*} x_n=\frac{12}{7}\left((n+1)H_n+1\right)\qquad\longleftrightarrow\qquad a_n=n+1\tag{6} \end{align*}

Third step: Adjustment for initial values

This solution for $x_n$ may not agree with the inital values $x_1$ and $x_2$. To accommodate arbitrary initial values we need to discover two extra degrees of freedom in the solution.

One degree of freedom can be observed in the first family of solutions. Combining $s=0$ with $s=1$ yields $$x_n=n+1\qquad\longleftrightarrow\qquad a_n=0$$ So any multiple of $n+1$ can be added to the solution in (6).

The second degree of freedom is not quite so obvious. Since $a_n=0$ we have a simplified recurrence for $x_n$,

\begin{align*} n(n-1)(n-2)x_n=12\sum_{1<k<n}(n-k)(k-1)x_{k-1}\tag{7} \end{align*}

Using a generating function, $G(z)$, for the sequence $x_n$, the convolution on the right of (7) is represented by the product $\frac{1}{(1-z)^2}$ corresponding to $(n-k)$ and $G^{\prime}(z)$ corresponding to $(k-1)x_{k-1}$. We obtain the differential equation $$G^{\prime\prime\prime}(z)=\frac{12}{(1-z)^2}G^{\prime}(z)$$

The nature of the equation suggests a solution of the form $G(z)=(1-z)^\alpha$, and testing this solution yields $\alpha=-2$ or $5$. The case $\alpha=-2$ corresponds to the previous observation that multiples of $n+1$ do not affect the solution. But for $\alpha =5$ we obtain an unusual solution that is zero after its first five values:

$$x_1=-5,\quad x_2=10,\quad x_3=-10,\quad x_4=5,\quad x_5=-1$$

This provides a second degree of freedom and yields the final solution

$$x_n=\frac{12}{7}\left((n+1)H_n+1\right)+c_1(n+1)+c_2(-1)^n\binom{5}{n}$$

where $c_1$ and $c_2$ are determined by the initial conditions.

Conclusion: It's instructive to see which candidates were selected for the repertoire in the first step. And it's very instructive to see how to cope with the inadequacy of the first family and select $x_n=(n-1)^{\underline{t}}H_n$ to extend the repertoire. But the last step indicates (at least for me) that finding a solution is also an art based upon a high level of creativity and a high level of experience.

Solution 2:

I know this is kinda old, but other explanations given here are needlessly complex.

Basically, our goal is to find a general function f for any $\alpha$, $\beta$, and $\gamma$, given the recurrence

\begin{align} f(1) &= \alpha\\ f(2n) &= 2f(n)+\beta\\ f(2n+1) &= 2f(n)+\gamma \end{align}

and the knowledge that there are some functions $A$, $B$, and $C$ such that

$$ f(n) = A(n) \alpha + B(n) \beta + C(n) \gamma. $$

We can find such functions by looking at special cases where we know $\alpha$, $\beta$, and $\gamma$, and where $f$ is easy to compute. Then combine such equations to solve for $A$, $B$, and $C$. The book has the new $f$ value listed first, then derives the values of the variables which satisfy that equation, but for clarity I will begin by defining values for the variables, then wave my hand and get the function $f$ which satisfies the recurrence under those variables. The first case (in the book) has,

\begin{align} \alpha &= 1\\ \beta &= 0\\ \gamma &= 0\\ \end{align} So that for $n=2^m+l$,
\begin{align} f(n) = 2^m \end{align} Plugging in the values we get, \begin{align} f(n) &= A(n) \alpha + B(n) \beta + C(n) \gamma\\ 2^m &= A(n) \end{align}

Next we make, \begin{align} \alpha &= 1,\\ \beta &= -1,\\ \gamma &= -1. \end{align} So that, \begin{align} f(n) = 1. \end{align} Plugging in the values we get, \begin{align} f(n) &= A(n) \alpha + B(n) \beta + C(n) \gamma\\ 1 &= A(n)-B(n)-C(n) \end{align}

And finally we take, \begin{align} \alpha &= 1\\ \beta &= 0\\ \gamma &= 1 \end{align} So that, \begin{align} f(n) = n \end{align} Plugging in the values we get, \begin{align} f(n) &= A(n) \alpha + B(n) \beta + C(n) \gamma\\ n&= A(n) + C(n) \end{align}

Now we have, \begin{align} A(n) &= 2^m\\ 1 &= A(n) - B(n) -C(n)\\ n &= A(n) + C(n) \end{align} Remembering that $n = 2^m + l$ we get, \begin{align} A(n) &= 2^m\\ B(n) &= 2^m -1-l\\ C(n) &= l\\ \end{align} For a final equation of \begin{align} f(2^m+l) = 2^m\alpha + (2^m-1-l)\beta + l\gamma \end{align} QE-motherfunctioning-D!