简介
成套方法（repertoire method）可以用来求解一大类的递归式的封闭形式，由于和式也可以化为特殊的递归式，因而该方法对于处理和式也有很好的效果，具体而言，对于如下类似形式的递归式： \[ f(n) = \begin{cases} \alpha & n = 0 \\ f(n - 1) + \beta + \gamma n + \delta n^2 \cdots & n > 0 \end{cases} \] 我们总是可以大胆地猜想：\(f(n)\) 或许有着如下的封闭形式： \[ f(n) = A(n)\alpha + B(n)\beta + C(n)\gamma + D(n)\delta \cdots \] 成套方法的精髓就是，试图用几组特殊的 \(f(n)\) （可以让我们相对容易地解出 \(\alpha,\beta\) 等的值），来推测 \(A(n), B(n)\) 等之间的关系，由于在上面的式子当中 \(A(n),B(n)\) 等都是线性组合的，因而最后我们会得到一组线性方程，求解这一组线性方程我们可以得出 \(A(n),B(n)\cdots\) 从而解出递归式的特殊形式。这是一个特殊→一般→特殊→一般→特殊的方法，十分巧妙。
例子：求解 \(\sum_{k=1}^n k^2\)
这是一个和式，但是不打紧，我们可以把它处理成递归式。
令 \(f(n) = \sum_{k = 1}^n k^2\)，那么有等价定义 \[ f(n) = \begin{cases} 0 & n = 0 \\ f(n - 1) + n^2 & n > 0 \end{cases} \] 可以看到从和式到递归式的转化是十分自然的。
这个递归式自然是满足最前面的形式的，其中 \(\alpha = \beta = \gamma = 0, \delta = 1\)，我们先着手求解一般情况，选取几组 “特殊的”\(f(n)\)：
首先令 \(f(n) = 1\)，代入最开始的定义： \[ \begin{cases} 1 &= \alpha \\ 1 &= 1 + \beta + \gamma n + \delta n^2 \end{cases} \] 显然有 \(\alpha = 1, \beta = \gamma = \delta = 0\)，再把他们带入我们认为的 “通用形式”： \[ f(n) = 1 = A(n)\cdot 1 + B(n)\cdot 0 + C(n)\cdot 0 + D(n)\cdot 0 \\ \Rightarrow A(n) = 1 \] 很好，我们现在得到一组 \(A(n),B(n),C(n),D(n)\) 的线性关系了，还需要三组！
令 \(f(n) = n\) \[ \begin{cases} 0 &= \alpha \\ n &= n - 1 + \beta + \gamma n + \delta n^2 \\ \end{cases} \\ \begin{aligned} &\Rightarrow \alpha = \gamma = \delta = 0, \beta = 1 \\ &\Rightarrow B(n) = n \end{aligned} \] 令 \(f(n) = n^2\)： \[ \begin{cases} 0 &= \alpha \\ n^2 &= (n - 1) ^ 2 + \beta + \gamma n + \delta n^2 \\ &= n^2 - 2n + 1 + \beta + \gamma n + \delta n^2 \end{cases} \\ \begin{aligned} &\Rightarrow \alpha = \delta = 0, \beta = -1, \gamma = 2 \\ &\Rightarrow -B(n) + 2C(n) = n^2 \end{aligned} \] 最后，令 \(f(n) = n^3\)： \[ \begin{cases} 0 &= \alpha \\ n^3 &= (n - 1) ^ 3 + \beta + \gamma n + \delta n^2 \\ &= n^3 - 3n^2 + 3n - 1 + \beta + \gamma n + \delta n^2 \end{cases} \\ \begin{aligned} &\Rightarrow \alpha = 0, \beta = 1,\gamma = -3, \delta = 3 \\ &\Rightarrow B(n) - 3C(n) + 3D(n) = n^3 \end{aligned} \] 最后，把这四组关系结合起来： \[ \left\{\begin{aligned} A(n) && && && &= 1 \\ &&B(n) &&&& &= n \\ &-&B(n) &+& 2C(n) && &= n^2 \\ &&B(n) &-& 3C(n) &+& 3D(n) &= n^3 \end{aligned}\right. \] 非常简单的线性方程组，解得： \[ \begin{cases} A(n) = 1 \\ B(n) = n \\ C(n) = \frac{n^2 + n}{2} \\ D(n) = \frac{2n^3 + 3n^2 + n}{6}\\ \end{cases} \] 这个时候，回到我们要解的递归式，其中 \(\alpha = \beta = \gamma = 0, \delta = 1\), 因此 \[ \begin{aligned} f(n) = \sum_{k = 1}^n k^2 = D(n) &= \frac{2n^3 + 3n^2 + n}{6} \\ &= \frac{n(n + 1)(2n + 1)}{6} \end{aligned} \] 求解到此结束，可以看到这个公式和我们的常识一致。虽然以上过程看似繁琐，但是注意我们已经求解了一大类的问题，因为 \(A(n),B(n),C(n),D(n)\) 是不会因 \(\alpha, \beta, \gamma, \delta\) 而变化的！，现在，对于任何的二次多项式的和式或者递归式我们都可以飞快地计算出其封闭形式。更有用的是，不仅仅是二次三项式，如果我们以后要处理三次多项式（意味着我们要加入 \(\varepsilon\) 和 \(E(n)\)），之前的 \(A(n),B(n),C(n),D(n)\) 的解也不会变化，因而只要继续带入 \(f(n) = n^4\) 即可！ （这是显然的）
注意：为了找出线性关系，我们也可以先找出 \(\alpha, \beta\) 等的一组特解，然后基于这个解计算 \(f(n)\)，这和代入特殊 \(f(n)\) 然后反解 \(\alpha, \beta\) 是等价的！
思考：为什么可以这样做 ？
为什么几个看似毫不相关的 \(f(n)\) 可以指导我们正在处理的特殊情形，注意到我们的步骤：
- 将特殊 \(f(n)\) 带入递归式的定义，解出 \(\alpha, \beta, \gamma, \delta\cdots\)
- 将 1 的解带入假设的封闭形式，求出 \(A(n), B(n), C(n), D(n)\cdots\) 的关系
注意到，我们在第一步解出了 \(\alpha, \beta\) 等的值，说明此时我们的特殊 \(f(n)\) 本来就是以上的递归式定义可以表出的，而我们假设的通用形式是对任何一组参数通用的，因此求解出来的线性关系也是通用的。
思考：真的 “万能” 和 “机械化” 吗？
成套方法从刚刚的示例可以看到似乎是非常机械化的，但是其实不然，《具体数学》中有言，成套方法对于线性的递归式最为有效，因此 \(f(n - 1)\) 前是不能有系数的（不然直觉上通用形式里就会出现棘手的指数项），但是这不妨碍我们处理和式，其次，对于一开始的 “通用形式” 的构造和特殊 \(f(n)\) 的构造其实不是那么简单的工作，对于多项式，我们可以很简单地构造多项式形式的 “通用形式”，但是如果是：
\[ \sum_{k = 1}^n (-1)^k k^2 \] 最上面的通用形式就不管用了！我们需要自己寻找适合的通用定义和特殊函数值进行求解（这也是《具体数学》当中的习题），虽然找到之后的过程倒是非常地机械化没错。
思考：作为算法实现的复杂度？
我们仅在这里思考以上方法在多项式情况下的特例。
成套方法分为三步走：
- 构造线性方程
- 解线性方程
- 回代
第一步，由于是多项式的情况，观察之前的特例并结合二项式定理可以得到， 如果我们带入 \(f(n) = n^k\) 的情况，对于对应 \(n^m\) 的多项式系数（类似 \(A(n), B(n)\)），其系数为（在 \(m \neq k\) 时，在 \(m = k\) 时系数自然就是 0 了）：
\[ -\binom{k}{m}(-1)^{k - m} \] 因此，配合杨辉三角递推组合数，这一部分的时间复杂度可以做到 \(O(n^2)\)。
第二步，考虑到我们解的线性方程当中含有多项式，因此需要采用系数向量的表示方法，基本算数运算代价变为 \(O(n)\)，但是注意到线性方程组列出时已经是简化阶梯形式，因此不需要高斯消元，只需要代入消元，时间复杂度是 \(O(n^2)\cdot O(n) = O(n^3)\)。
第三步的复杂度自然是 \(O(n^2)\)。
因此，基于成套方法的算法的综合复杂度为 \(O(n^3)\)。