成套方法

Posted on 2018-11-09 Edited on 2022-06-14 Views:

简介

成套方法（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) = A(n)\alpha + B(n)\beta + C(n)\gamma + D(n)\delta \cdots$

成套方法的精髓就是，试图用几组特殊的

（可以让我们相对容易地解出 $\alpha,\beta$ 等的值），来推测

等之间的关系，由于在上面的式子当中

等都是线性组合的，因而最后我们会得到一组线性方程，求解这一组线性方程我们可以得出 $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$

很好，我们现在得到一组

的线性关系了，还需要三组！

令 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}$

令

：

$\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}$

最后，令

：

$\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}$

求解到此结束，可以看到这个公式和我们的常识一致。虽然以上过程看似繁琐，但是注意我们已经求解了一大类的问题，因为是不会因 $\alpha, \beta, \gamma, \delta$ 而变化的！，现在，对于任何的二次多项式的和式或者递归式我们都可以飞快地计算出其封闭形式。更有用的是，不仅仅是二次三项式，如果我们以后要处理三次多项式（意味着我们要加入 $\varepsilon$ 和

），之前的的解也不会变化，因而只要继续带入即可！ （这是显然的）

注意：为了找出线性关系，我们也可以先找出 $\alpha, \beta$ 等的一组特解，然后基于这个解计算，这和代入特殊然后反解 $\alpha, \beta$ 是等价的！

思考：为什么可以这样做？

为什么几个看似毫不相关的 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) 的构造其实不是那么简单的工作，对于多项式，我们可以很简单地构造多项式形式的“通用形式”，但是如果是：