Repertoire Method for Solving Recurrences

《具体数学：计算机科学基础（第二版）》第一章的“约瑟夫问题”中，介绍了一种求解递归式的奇妙技巧 —— Repertoire Method 。这种技巧帮助我们将特殊解推向一般解：通过一些已知其解的参数函数，从特殊的情形推向一般的情形。

求解约瑟夫问题

以约瑟夫问题为例子，书中给出了如下的递推式：

\begin{equation} \begin{array}{rll} J(1) & = 1 & \\ J(2n) & = 2J(n) - 1 & (n \geqslant 1) \\ J(2n + 1) & = 2J(n) + 1 & (n \geqslant 1) \\ \end{array} \end{equation}

列举已知解

我们按照递归式 $(1)$ ，获得几组解：


$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
$J(n)$	1	1	3	1	3	5	7	1	3	5	7	9	11	13	15	1

观察与推测

从上述表格可以看到， $J(n)$ 以 $2$ 的幂分组且每组总以 $J(n) = 1$ 开始，所以有 $J(2^{m}) = 1，m \geqslant 0$ 。又观察到，每组后续的数据每个以递增 $2$ 的速度发生变化。那么，我们可以先把 $n$ 改写成 $n = 2^{m} + l$ ，其中 $2^{m}$ 显然要小于等于 $n$ 的 $2$ 的最大幂， $l$ 则是去掉 $2^{m}$ 剩下的数，即 $l = n - 2^{m}$ 。

因此，我们可以推断递归式 $(1)$ 的解可能是：

\begin{equation} \begin{array}{lll} J(2^{m} + l) & = 2l + 1 & (m \geqslant 0, 0 \leqslant l < 2^{m}) \\ \end{array} \end{equation}

现在我们对 $m$ 使用归纳法来给出上式 $(2)$ 的证明：

$\because$ 当 $m = 0$ 时，有 $l = 0$ $\therefore$ $J(2^{0} + 0) = 2 \times 0 + 1 = 1$

$\because$ 当 $m > 0$ 且 $2^{m} + l = 2n$ 时，有 $l$ 为偶数又 $\because$ 递归式 $(1)$ 定义了 $J(2n) = 2J(n) - 1$ 且根据归纳假设 $(2)$ 有 $J(2^{m} + l) = 2l + 1$

\begin{array}{rl} \therefore J(2^{m} + l) & = 2J(2^{m - 1} + l / 2) - 1 \\ & = 2 \times (2 \times l / 2 + 1) - 1 \\ & = 2l + 1 \end{array}

同理， $\because$ 当 $m > 0$ 且 $2^{m} + l = 2n + 1$ 时，有 $l$ 为奇数又 $\because$ 递归式 $(1)$ 定义了 $J(2n + 1) = 2J(n) + 1$

\begin{array}{rl} \therefore J(2^{m} + l) & = 2J(2^{m - 1} + (l - 1) / 2) + 1 \\ & = 2 \times (2 \times (l - 1) / 2 + 1) + 1 \\ & = 2l + 1 \end{array}

综上可证，式子 $(2)$ 假设成立

推广：引入通用参数

通过引入常数 $\alpha$ 、 $\beta$ 、 $\gamma$ ，我们把递归式 $(1)$ 改写成更具一般性的递归式 $(2)$ ：

\begin{equation} \begin{array}{rll} f(1) & = \alpha & \\ f(2n) & = 2f(n) + \beta & (n \geqslant 1) \\ f(2n + 1) & = 2f(n) + \gamma & (n \geqslant 1) \\ \end{array} \end{equation}

列举已知解

我们从 $f(1) = \alpha$ 入手，求出多个 $f(n)$ 的结果并列出以下表格：

$n$	$f(n)$	$\alpha$ 系数	$\beta$ 系数	$\gamma$ 系数
1	$(1)\alpha$	1	0	0
2	$(2)\alpha + (1)\beta + (0)\gamma$	2	1	0
3	$(2)\alpha + (0)\beta + (1)\gamma$	2	0	1
4	$(4)\alpha + (3)\beta + (0)\gamma$	4	3	0
5	$(4)\alpha + (2)\beta + (1)\gamma$	4	2	1
6	$(4)\alpha + (1)\beta + (2)\gamma$	4	1	2
7	$(4)\alpha + (0)\beta + (3)\gamma$	4	0	3
8	$(8)\alpha + (7)\beta + (0)\gamma$	8	7	0
9	$(8)\alpha + (6)\beta + (1)\gamma$	8	6	1

观察与推测

观察发现， $\alpha$ 系数不超过 $n$ 的 $2$ 的最大幂，而 $\beta$ 系数则不断递减至 $0$ ， $\gamma$ 则与之相反，从 $0$ 开始递增。现在我们把 $f(n)$ 的三个系数关系单独抽离出来，然后改写成如下形式：

\begin{equation} f(n) = A(n)\alpha + B(n)\beta + C(n)\gamma \end{equation}

同样，我们尝试观察规律，可以得到以下等式：

\begin{equation} \begin{array}{rl} A(n) & = 2^{m} \\ B(n) & = 2^{m} - 1 - l \\ C(n) & = l \\ \end{array} \end{equation}

现在我们对 $m$ 使用归纳法，给出证明。从列举出来的已知解中选出一个特解 $(\alpha, \beta, \gamma) = (1, 0, 0)$ ，可以得到：

\begin{equation} f(n) = A(n) \end{equation}

那么递归式 $(3)$ 则转换成：

\begin{equation} \begin{array}{rrl} f(1) = & A(n) & = 1 \\ f(2n) = & A(2n) & = 2A(n) \\ f(2n + 1) = & A(2n + 1) & = 2A(n) \end{array} \end{equation}

$\because n = 2^{m} + l$ $\therefore$ 当 $m = 0$ 时，有 $A(2^{0} + l) = A(1 + l)$ 又 $\because 0 \leqslant l < 2^{m}$ ，有 $l = 0$ $\therefore A(1) = 1$

当 $m > 0$ 且 $2^{m} + l = 2n$ 时，有

\begin{array}{ll} A(2^{m} + l) & = 2A(n) \\ & = 2A(2^{m - 1} + l / 2) \\ & = 2 \times 2^{m - 1} \\ & = 2^{m} \end{array}

当 $m > 0$ 且 $2^{m} + l = 2n + 1$ 时，有

\begin{array}{ll} A(2^{m} + l) & = 2A(n) \\ & = 2A(2^{m - 1} + (l - 1) / 2) \\ & = 2 \times 2^{m - 1} \\ & = 2^{m} \end{array}

综上所述， $A(n) = 2^{m}$ 假设成立

因而，我们可以得到最终的解，其中 $m \geqslant 0$ 且 $0 \leqslant l < 2^{m}$ ：

\begin{equation} \begin{array}{lrl} f(n) & & = A(n)\alpha + B(n)\beta + C(n)\gamma \\ & = f(2^{m} + l) & = 2^{m}\alpha + (2^{m} - 1 - l)\beta + l\gamma \\ & & = 2^{m}(\alpha + \beta) - (l + 1)\beta + l\gamma \end{array} \end{equation}

回顾下：（1）我们计算出前 N 个递归式的值，列出表格；（2）观察表格的数据，尝试找些规律；（3）用这些规律把递归式改写成 closed form（封闭形式）；（4）用归纳法等证明 closed form。

巧妙的求解方法：Repertoire Method（取值法）

这里的“取值法”中文翻译采用的是《算法分析导论》中文版，因为比较直观地表达了这种方法的核心，而《具体数学》中文版对应的翻译则是“成套方法”。

《具体数学》介绍了另一种求解递归式 $(4)$ 的方法：Repertoire Method。简单概括，我们把递归式的解看成由多个线性函数的解分别通过一系列参数组合而成，而这些线性函数由我们自己构造，从而可以求出这一系列参数的值，最终得到递归式的解（这个过程反过来也是可行的：通过已知的参数来求解未知的线性函数，本文就不具体描述这个过程，请参考原书）。

This approach illustrates a surprisingly useful repertoire method for solving recurrences. First we find settings of general parameters for which we know the solution; this gives us a repertoire of special cases that we can solve. Then we obtain the general case by combining the special cases. We need as many independent special solutions as there are independent parameters… Concrete Mathematics, 2nd Edition

这个描述比较抽象，在后文将结合例子对上述描述进行解释，我们先按照原书以递归式 $(3)$ 举例，取两个函数 $f(n) = 1$ 和 $f(n) = n$ ，尝试能否得到一组参数方程。

当 $f(n) = 1$ 时，有

\begin{array}{ll} f(1) & = \alpha = 1 \\ f(2n) & = 2f(n) + \beta \\ & = 2 \times 1 + \beta \\ & = 1 \\ f(2n + 1) & = 2f(n) + \gamma \\ & = 2 \times 1 + \gamma \\ & = 1 \end{array}

解得 $\alpha = 1, \beta = -1, \gamma = -1$

代入式子 $(4)$ ，则 $f(n) = A(n) - B(n) - C(n) = 1$

当 $f(n) = n$ 时，有

\begin{array}{ll} f(1) & = \alpha = 1 \\ f(2n) & = 2f(n) + \beta \\ & = 2 \times n + \beta \\ & = 2n \ f(2n + 1) & = 2f(n) + gamma \\ & = 2 \times n + gamma \\ & = 2n + 1 \end{array}

解得 $\alpha = 1, \beta = 0, \gamma = 1$

代入式子 $(4)$ ，则 $f(n) = A(n) + C(n) = n$

另外，由归纳假设可证得， $A(n) = 2^{m}$ ，其中 $n = 2^{m} + l$ 且 $0 \leqslant l < 2^{m}$ ，那么我们获得了 3 个方程：

\begin{array}{rl} A(n) & = 2^{m} \\ A(n) - B(n) - C(n) & = 1 \\ A(n) + C(n) & = n \\ \end{array}

现在可以解得：

\begin{array}{rlll} A(n) & = 2^{m} & & \\ C(n) & = n - A(n) & = n - 2^{m} & = l \\ B(n) & = 2^{m} - 1 - l & & \end{array}

最后我们得到了与式子 $(8)$ 相同的递归式的解。现在，我们用这个一般解 $(8)$ 来求解约瑟夫问题的递归式 $(1)$ ：

由递归式 $(1)$ 可得： $\alpha = 1, \beta = -1, \gamma = 1$

代入式子 $(8)$ 得：

\begin{array}{rlll} f(n) & = f(2^{m} + l) \\ & = 2^{m}(1 + (-1)) - (l + 1) \times (-1) + l \times 1 \\ & = 2l + 1 \end{array}

回顾下，在这个求解过程中，（1）我们取 $f(n) = 1$ 以及 $f(n) = n$ ；（2）代入递归式 $(3)$ ；（3）求得一组参数值 $\alpha$ 、 $\beta$ 、 $\gamma$ ；（4）分别代入式子 $(4)$ ，得到方程组；（5）求解这个方程组，得到 $A(n)$ 、 $B(n)$ 和 $C(n)$ ；（6）组合参数与对应的函数，得到递归式的解。

…the so-called repertoire method, where we use known functions to find a family of solutions similar to the one sought, which can be combined to give the answers. This method primarily applies to linear recurrences… An Introduction to The Analysis of Algorithms, 2nd Edition

到目前为止，我们已经了解到，递归式的解可以由一组线性函数组合而成，因而有：

\begin{array}{rl} a_{n} & = A_{1}(n)·\alpha_{1} + A_{2}(n)·\alpha_{2} + \cdots + A_{k}(n)·\alpha_{k} \\ & =\sum_{i=1}^{k}A_{i}(n)·\alpha_{i} \end{array}

可惜《具体数学》轻描淡写地介绍了这种方法，看得云里雾里。在另外一本书籍《算法分析导论（第二版）》找到了进一步的说明，作者列举了 Repertoire Method 的步骤：

Relax the recurrence by adding an extra functional term
Substitute known functions into the recurrence to derive identities similar to the recurrence
Take linear combinations of such identities to derive an equation identical to the recurrence

说得还是挺抽象的，我们需要更多的例子来进一步理解这种技巧。不幸的是，由于《算法分析导论》的作者在“勘误列表”指出，书中给出的例子“is bad; needs to be replaced”，我只好借用发表在 StackExchange 关于 Repertoire Method 问题的回答。

StackExchange 回答者给出以下例子（本文在求解过程中做了稍微的修改，以符合上文的描述）：

\begin{array}{ll} a_{n} = a_{n-1} + 2n^{2} + 7 & (n > 0 且 a_{0} = 7) \end{array}

首先，泛化这个递归式。令 $f(n) = 2n^{2} + 7$ ，则 $a_{n} = a_{n-1} + f(n)$ ，即 $f(n) = a_{n} - a_{n-1} = 2n^{2} + 7$ ；然后，我们尝试取几个不同的 $a_{n}$ 值，列出以下表格：

$a_{n}$	$f(n) = a_{n} - a_{n-1}$
$1$	$0$
$C(n) = n$	$1$
$B(n) = n^{2}$	$2n-1$
$A(n) = n^3$	$3n^{2}-3n+1$

观察 $f(n) = 2n^{2}+7$ 存在一个平方项 $n^2$ 和一个常数 $7$ ，那么，当 $a_{n}=n^{3}$ 时恰好有 $f(n) = 3n^{2}-3n+1$ ，它提供了一个平方数 $n^{2}$ 。但是，为此也引入了一个 $n$ ，它不存在于 $f(n)$ ，我们需要消除它。通过表格可以发现，当 $a_{n}=n^{2}$ 时恰好有 $2n-1$ ，它提供了一个 $n$ ，这样我们就有机会通过参数（即 $\beta$ ）将额外引入的 $n$ 消除。最后，当 $a_{n}=1$ 时恰好有 $f(n)=1$ ，它提供了一个常数 $1$ 。

这样我们找到了一套特殊函数（ a repertoire of special cases that we can solve ）： $A(n) = n^3$ 、 $B(n) = n^{2}$ 和 $C(n) = n$ 。

现在，我们组合这几个函数（ combining the special cases ）,令 $a_{n} = A(n)\alpha + B(n)\beta + C(n)\gamma$ ，则

\begin{equation} a_{n} = \alpha n^3 + \beta n^{2} + \gamma n \end{equation}

现在我们开始解这三个参数 $\alpha$ 、 $\beta$ 和 $\gamma$ ：

对 $f(n) = 2n^{2}+7$ ，存在三种解（ find settings of general parameters for which we know the solution ）：

当 $f(n)=1$ ，有解 $a_{n}=n$
当 $f(n)=2n-1$ ，有解 $a_{n}=n^2$
当 $f(n)=3n^{2}-3n+1$ ，有解 $a_{n}=n^3$

则

\begin{array}{rl} f(n) & = 2n^{2}+7 \\ & = \alpha (3n^{2}-3n+1) + \beta (2n-1) + \gamma (1) \\ & = 3 \alpha n^{2} + (-3 \alpha + 2 \beta) n + (\alpha - \beta + \gamma) \\ \end{array}

对应的系数方程，有

\begin{cases} 3\alpha = 2 \\ -3\alpha + 2\beta = 0 \\ \alpha - \beta + \gamma = 7 \end{cases}

解得：

\alpha = \frac{2}{3}, \beta = 1, \gamma = \frac{22}{3}

代入式子 $(9)$ ，得：

\begin{equation} \begin{array}{ll} a_{n} & = \frac{2}{3} n^3 + n^{2} + \frac{22}{3} n \\ & = \frac{1}{3} n (2 n^2 + 3 n + 22) \end{array} \end{equation}

最后，我们检验式子 $(10)$ 的初始值： $a_{0}=0$ ，不符合原递归式 $a_{0}=7$ 。因此，我们需要调整式子 $(10)$ ，即在原式子追加 $7$ ，得到：

a_{n} = \frac{1}{3} n (2 n^2 + 3 n + 22) + 7

回顾下，在这个求解过程中，（1）我们尽可能取多个 $a_{n}$ 值，得到对应的 $f(n)$ 的值，然后列成表格；（2）观察 $f(n)$ 的构成，从表格中选取合适的 $a_{n}$ ，有多少种 $a_{n}$ 就对应多少个参数需要求解；（3）每种 $a_{n}$ 所对应的 $f(n)$ 与其参数组合，然后与原式 $f(n)$ 建立等式，即可得到一组参数方程；（4）组合参数及其 $a_{n}$ 得到递归式的 closed form；（5）检查这个 form 的初始值与原递归式是否一致，如果不同，则调整结果，把缺少的项补上或者去掉，最后得到递归式的解。

按照这个过程，借用一篇博文的例子再做说明：

\begin{array}{ll} a_{n} = a_{n-1} + n^3 & (n > 0 且 a_{0} = 0) \end{array}

首先，令 $f(n) = n^3$ ，则有 $f(n) = a_{n} - a_{n-1}$ 。建立 $a_{n}$ 与 $f(n) = a_{n} - a_{n-1}$ 的关系表：

$a_{n}$	$f(n) = a_{n} - a_{n-1}$
$1$	$0$
$D(n)=n$	$1$
$C(n)=n^{2}$	$2n-1$
$B(n)=n^3$	$3n^{2}-3n+1$
$A(n)=n^4$	$4n^{3}-6n^{2} +4n-1$

观察 $f(n)=n^{3}$ ，只存在一个三次方的项 $n^{3}$ ，当 $a_{n}=n^4$ 时恰好提供了一个 $n^{3}$ ；但是我们却为此引入 $n^{2}$ 、 $n$ 和 $1$ 。所以我们需要额外的三个参数来消除这几项。从表格中，我们可以继续选用 $a_{n}=n^3$ 、 $a_{n}=n^2$ 和 $a_{n}=n$ 。

把上述候选的 $a_{n}$ 分别设为 $A(n)$ ， $B(n)$ ， $C(n)$ 和 $D(n)$ ，则 $a_{n} = A(n) \alpha + B(n) \beta + C(n) \gamma + D(n) \lambda + c$ ，其中 $c$ 将按照原递归式的初始值对结果进行调整，则：

\begin{equation} a_{n} = \alpha n^4 + \beta n^{3} + \gamma n^{2} + \lambda n + c \end{equation}

现在我们开始求解对应的四个参数 $\alpha$ 、 $\beta$ 、 $\gamma$ 和 $\lambda$ ：

对 $f(n) = n^{3}$ ，存在四种解：

当 $f(n)=1$ ，有解 $a_{n}=n$
当 $f(n)=2n-1$ ，有解 $a_{n}=n^2$
当 $f(n)=3n^{2}-3n+1$ ，有解 $a_{n}=n^3$
当 $f(n)=4n^{3}-6n^{2}+4n-1$ ，有解 $a_{n}=n^3$

则

\begin{array}{rl} f(n) & = n^{3} \\ & = \alpha (4n^{3}-6n^{2}+4n-1) + \beta (3n^{2}-3n+1) + \gamma (2n-1) + \lambda (1) \\ & = 4 \alpha n^{3} + (-6 \alpha + 3 \beta) n^{2} + (4 \alpha - 3 \beta + 2 \lambda) n + (- \alpha + \beta - \gamma + \lambda) \\ \end{array}

对应的系数方程，有

\begin{cases} 4 \alpha = 1 \\ -6 \alpha + 3 \beta = 0 \\ 4 \alpha - 3 \beta + 2 \lambda = 0 \\ - \alpha + \beta - \gamma + \lambda = 0 \end{cases}

解得：

\alpha = \gamma = \frac{1}{4}, \beta = \frac{1}{2}, \lambda = -\frac{1}{2}

代入式子 $(11)$ ，得：

\begin{array}{rl} a_{n} & = \frac{1}{4} n^{4} + \frac{1}{2} n^{3} + \frac{1}{4} n^{2} - \frac{1}{2} + c \\ & = \frac{1}{4} n^{2} (n^{2} + 2 n + 1) - \frac{1}{2} + c \\ & = \frac{1}{4} n^{2} (n + 1)^{2} - \frac{1}{2} + c \end{array} \\

$\because a_{0} = 0 \therefore c = \frac{1}{2}$ ，代入上式，得：

a_{n} = \frac{1}{4} n^{2} (n + 1)^{2}

总结

《具体数学》作者先以“猜想与归纳”（Guess and Induction）的方法求解递归式，步骤如下：

计算前 N 个递归的结果，列成表格
观察表格，找出规律
整合规律，得到 closed form（封闭形式）即递归式的解
用归纳法等数学方法证明结果成立

接着，作者尝试了另一种方法，把递归式的解定义为一组线性函数及一组参数构成： $a_{n}=\sum_{i=1}^{k}A_{i}(n)·\alpha_{i}$ 。于是，递归式的求解问题转换成了求解线性函数或参数的问题。求解过程中，我们既可以固定线性函数来求参数，也可以固定参数来求线性函数。具体步骤如下：

令递归式的解为多个线性函数构成，设 $a_{n} = f(n) = A(n) \alpha + B(n) \beta + C(n) \gamma$
取多个 $a_{n}$ 的值，如 $a_{n}=1$ 、 $a_{n}=n$ 、 $a_{n}=n^2$ 等
分别代入原递归式，列出多组参数方程组，解得多组参数的值
每组参数的值代入 $f(n)$ ，列出线性函数的方程组，解得各个线性函数
把解得的线性函数与原递归式的参数代入 $f(n)$ ，即求得递归式的解

最后，按照《算法分析导论》作者的思路，同样以 Repertoire Method 求解，不过步骤稍有不同：

令递归式的解为多个线性函数构成，设 $a_{n} = \sum_{i=1}^{k}A_{i}(n)·\alpha_{i} + c$
把原递归式转换成 $a_{n} = g(a_{n-1}, a_{n-2}, ..., a_{0}) + f(n)$
取多个 $a_{n}$ 的值，如 $a_{n}=1$ 、 $a_{n}=n$ 、 $a_{n}=n^2$ 等，计算出 $f'(n) = a_{n} - g(a_{n-1}, a_{n-2}, ..., a_{0})$ 结果，然后建立成表格
观察原 $f(n)$ 的构成，从表格中选取合适的 $a_{n}$ 分别作为 $A_{i}(n)$ ，同时确定参数的个数 $k$ ，每个参数作为 $\alpha_{i}$ ，而 $a_{n}$ 所对应的 $f'(n)$ 值作为 $f'_{\alpha_{i}}(n)$
建立等式： $\sum_{i=1}^{k} \alpha_{i} · f'_{\alpha_{i}}(n) = f(n)$ ，列出一组参数方程，解出参数值
把参数值代入 $a_{n} = \sum_{i=1}^{k}A_{i}(n)·\alpha_{i} + c$ ，最后代入原递归式的初始值，求得 $c$

后记

《具体数学》第一章引入了 Repertoire Method 来求解递归式，据说在后续章节中频繁运用，那么熟悉这种技巧及其应用，有助于理解后续的章节，所以花了比较多的时间学习这种技巧，不过依然还有些问题未得到解决，比如：

Repertoire Method 的原理是什么？为什么递归式的解可以由多个线性函数组合？
如何更加合理地确定参数的个数？为什么《具体数学》只用了三个参数就足够了？（事实上本文的例子都可以默认用三个参数来解）
…

在《算法分析导论》提到了这种技巧的实际应用：求解快速排序的的递归式，具体求解过程可以参考 StackExchange 的回答。其他更多的例题可通过下面的“参考资料”获得。