# Repertoire Method for Solving Recurrences

## 求解约瑟夫问题

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

### 列举已知解

$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

### 观察与推测

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

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

$\because$ 当 $m > 0$ 且 $2^{m} + l = 2n$ 时，有 $l$ 为偶数

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

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

## 推广：引入通用参数

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

### 列举已知解

$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

### 观察与推测

$$$$f(n) = A(n)\alpha + B(n)\beta + C(n)\gamma$$$$

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

$$$$f(n) = A(n)$$$$

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

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

$\therefore A(1) = 1$

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

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

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

## 巧妙的求解方法：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

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

$f(n) = A(n) - B(n) - C(n) = 1$

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

$f(n) = A(n) + C(n) = n$

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

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

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

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

• 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

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

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

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

$$$$a_{n} = \alpha n^3 + \beta n^{2} + \gamma n$$$$

• 当 $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}$$

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

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

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

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

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

• 当 $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}$$

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

## 总结

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

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

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

## 后记

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