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.
Best Answer
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.
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*}
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.
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 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 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$.
Let's have a look at the repertoire:
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*}
Let's summarise
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 ... :-)
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*}
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*}
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.
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)$$
(... The following text is nearly verbatim from the book ...)
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*}
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$$
where $c_1$ and $c_2$ are determined by the initial conditions.