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.
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&amp;=a_0\\
x_n&amp;=a_n+x_{n-1},\quad n&gt;0
\end{align*}
  and we have another recurrence for $y_n$
  \begin{align*}
y_0&amp;=b_0\\
y_n&amp;=b_n+y_{n-1},\quad n&gt;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&amp;=3&amp;y_0&amp;=1\\
x_n&amp;=3+x_{n-1},\quad n&gt;0&amp;y_n&amp;=5n^2+1+y_{n-1},\quad n&gt;0
\end{align*}

then we also know by linearity that the solution of the recurrence
\begin{align*}
z_0&amp;=7\\
z_n&amp;=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&amp;=7\\
z_n&amp;=2n^2+7+z_{n-1},\quad n&gt;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&amp;=a_0\\
\mathcal{Z}_n&amp;=a_n+\mathcal{Z}_{n-1},\quad n&gt;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&amp;=0\\
n&amp;=a_n+n-1\quad n&gt;0
\end{align*}
and we find: $a_0=0$ and $a_n=1,n&gt;0$.


  We get the first candidate, let's say $x_n$ with
  
  \begin{align*}
x_0&amp;=0\\
x_n&amp;=1+x_{n-1},\quad n&gt;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&amp;=0\\
n^3&amp;=a_n+(n-1)^3\quad n&gt;0
\end{align*}
and we find $a_0=0$ and $a_n=3n^2-3n+1,n&gt;0$.


  We get the second candiate, let's say $y_n$ with
  
  \begin{align*}
y_0&amp;=0\\
y_n&amp;=3n^2-3n+1+y_{n-1},\quad n&gt;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&amp;=0\\
n^2&amp;=a_n+(n-1)^2\quad n&gt;0
\end{align*}
and we find $a_0=0$ and $a_n=2n-1,n&gt;0$.


  So we get the third candiate, let's say $u_n$ with
  
  \begin{align*}
u_0&amp;=0\\
u_n&amp;=2n-1+u_{n-1},\quad n&gt;0\tag{4}
\end{align*}


Let's have a look at the repertoire:


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


We observe when using an appropriate linear combination
\begin{align*}
a_n&amp;=2n^2+7\\
&amp;=\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&amp;=\frac{22}{3}x_n+\frac{2}{3}y_n+u_n+c_0\\
&amp;=\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&lt; k &lt;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}}&amp;=a_n+\frac{12}{n^{\underline{3}}}\sum_{1&lt; k &lt;n}(n-k)(k-1)^{\underline{s+1}}\\
&amp;=\ldots\\
&amp;=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}
&amp;x_n&amp;a_n\\
\hline\\
s=0\qquad&amp;1&amp;\qquad-1\\
s=1\qquad&amp;(n-1)&amp;\qquad2\\
s=2\qquad&amp;(n-1)(n-2)&amp;\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&amp;=a_n+\frac{12}{n^{\underline{3}}}\sum_{1&lt; k &lt;n}(n-k)(k-1)^{\underline{t+1}}H_{k-1}\\
&amp;=\ldots\\
&amp;=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.\\
&amp;\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}
&amp;x_n&amp;a_n\\
\hline\\
t=0\qquad&amp;H_n&amp;\qquad-H_n+\frac{5}{3}\\
t=1\qquad&amp;(n-1)H_n&amp;\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&lt;k&lt;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.
Lets take a recurrence relation for example
$f(0) = 0$
$f(n) = 1 + f(n - 1), n &gt; 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 &gt; 0$
lets first construct a table of values for $g(n)$
$g(0)$ -&gt; $0$
$g(1)$ -&gt; $1$
$g(2)$ -&gt; $3$
$g(3)$ -&gt; $6$
$g(4)$ -&gt; $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 &gt; 0$
Now lets construct a table of values for this recurrence $h(n)$
$h(0)$ -&gt; $0$
$h(1)$ -&gt; $2$
$h(2)$ -&gt; $5$
$h(3)$ -&gt; $9$
$h(4)$ -&gt; $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)$ -&gt; $0$
$h(1)$ -&gt; $2$
$h(2)$ -&gt; $5$
$h(3)$ -&gt; $9$
$h(4)$ -&gt; $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 &gt; 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 &gt; 0$
Now by sheer observation we can see that, in the original recurrence of
$h(n)$ we only see the variable &quot;$n$&quot; and the constant &quot;$1$&quot;, but in the modified recurrence of
$h(n)$ we have associated the variable &quot;$n$&quot; with another recurrence called $g(n)$ and
similarly we have associated the constant &quot;$1$&quot; with another recurrence called $f(n)$.
$n$ -&gt; $(n + g(n - 1))$
$1$ -&gt; $(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.