27
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The answer given by Markus is extremely helpful and deserves to be the accepted answer But if someone still doesn't get it and requires a more vidoe-type approach Then the following might help youtu.be/8WbpRwYcEf0 $\endgroup$ – Meherwan Gill Jul 28 '19 at 23:34
50
+50
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ This answer is awesome in every way. I finally get it! Thanks a lot! $\endgroup$ – Felipe Jacob Nov 17 '14 at 1:39
  • 1
    $\begingroup$ @Felipe Jacob: You're welcome! Good to see the answer is useful. :-) $\endgroup$ – Markus Scheuer Nov 17 '14 at 7:58
  • $\begingroup$ +1. Such clear presentation! I would have given more points if possible. This is akin to the linear superposition in solving linear PDE's. But of course, these are all under the umbrella of the linear vector space. $\endgroup$ – Hans Jul 23 '19 at 7:39
  • $\begingroup$ @Hans: Many thanks for your nice comment and the credit. $\endgroup$ – Markus Scheuer Jul 23 '19 at 8:06
  • $\begingroup$ Excellent write up @MarkusScheuer. Question: In the introduction, when you say "Then provided these recurrences are known", do you mean provided the closed form is known? $\endgroup$ – Fred Clausen Jan 28 at 4:11
0
$\begingroup$

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!

| cite | improve this answer | |
$\endgroup$
-1
$\begingroup$

Lets take a recurrence relation for example

$f(0) = 0$
$f(n) = 1 + f(n - 1), n > 0$

for this recurrence the closed form is

$f(n) = n$

lets take another recurrence relation for example

$g(0) = 0$
$g(n) = n + g(n - 1), n > 0$

lets first construct a table of values for $g(n)$

$g(0)$ -> $0$
$g(1)$ -> $1$
$g(2)$ -> $3$
$g(3)$ -> $6$
$g(4)$ -> $10$

By sheer observation, we get the closed form for $g(n)$

$g(n) = (n * (n + 1)) / 2$

Now lets take a third recurrence relation

$h(0) = 0$
$h(n) = n + 1 + h(n - 1), n > 0$

Now lets construct a table of values for this recurrence $h(n)$

$h(0)$ -> $0$
$h(1)$ -> $2$
$h(2)$ -> $5$
$h(3)$ -> $9$
$h(4)$ -> $14$

Now we would like to find a closed form for this recurrence relation h(n).
But it is not very clear to find the closed form by sheer observation.

But first let's try out a formula.

$h(n) = ((n * (n + 1)) / 2) + n$

Considering the above formula is a closed form for $h(n)$. lets create another table using the above formula

$h(0)$ -> $0$
$h(1)$ -> $2$
$h(2)$ -> $5$
$h(3)$ -> $9$
$h(4)$ -> $14$

and viola the values match. If we properly observe the closed form of $h(n)$, we can see that it consists of two closed form formulas.

first one being closed form of $g(n)$
$g(n) = (n * (n + 1)) / 2$

second one being closed form of $f(n)$
$f(n) = n$

It turns out that $h(n)$ is a linear combination of the two recurrences $f(n)$ and $g(n)$.
We can write $h(n)$ in closed form as follows

$h(n) = ((n * (n + 1)) / 2) + n$
$h(n) = g(n) + f(n)$, here $f(n)$ and $g(n)$ are in closed form

or we can also write $h(n)$ in recurrence form as

$h(0) = 0$
$h(n) = (n + g(n - 1)) + (1 + f(n - 1))$, $n > 0$ here $f(n)$ and $g(n)$ are in recurrence form

now lets compare the above recurrence with the original recurrence of $h(n)$

$h(0) = 0$
$h(n) = n + 1 + h(n - 1), n > 0$

Now by sheer observation we can see that, in the original recurrence of $h(n)$ we only see the variable "$n$" and the constant "$1$", but in the modified recurrence of $h(n)$ we have associated the variable "$n$" with another recurrence called $g(n)$ and similarly we have associated the constant "$1$" with another recurrence called $f(n)$.

$n$ -> $(n + g(n - 1))$
$1$ -> $(1 + f(n - 1))$

From this we can say that if we are unable to find the closed form of some recurrence relation by just sheer observation. Then, we can actually look into the constants and the variables and try to make small recurrence relations for those individual terms. Once, we figure out these individual recurrence relation of every term and also find their corresponding closed form. We can then combine the closed forms of those bits of recurrence relation to get the closed form of the orginal recurrence relation.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.