Recurrent Problems

---

本章介绍了三个问题：Hanoi 塔，直线切割平面，Josephus 环.

前两个问题是个引子，主要讲了怎么分析问题，从小的问题入手 [look at small cases], 找到更 general 问题的通解.

The Tower of Hanoi

如果要移动 $0$ 层的塔，那步骤当然是 $0$. 即:

$T_0 = 0$.

我们要将一个 $n$ 层的塔转移到另一根 peg 上，就需要先将其上的 $n - 1$ 层塔转移到另一根 peg 上，然后移动第 $n$ 个 disk, 再将 $n - 1$ 层塔移动到 nth disk 所在的 peg 上。于是，设移动 $n$ 层塔到另一根 peg 上所需的步骤为 T(n), 则我们可以在最多 $2T_{n-1} + 1$ 步内完成。由此得到:

$T_n \leq 2T_{n-1} + 1$.

我们由以上的推理只得到了上界，那下界呢？

由于我们必须得在某一步时将 nth disk 移动，所以在这步之前前 $n - 1$ 层塔的移动必须完成，也即必须花费 $T_{n-1} + 1$. 在这之后，虽然我们可以多次移动 nth disk, 但在最后一次移动后必须将 $n-1$ 层塔移到其上，所以又将花费 $T_{n-1}$. 由此得到:

$T_n \geq 2T_{n-1} + 1$.

有 boundary value, 有 equation for the general value, 我们就得到了一个 recurrence:

$T_0 = 0$;
$T_n = 2T_{n-1} + 1$, for $n \geq 0$.

然而仅有递推解很难满足我们快速计算的需求，因为我们还想找出一个 closed form.

什么是 closed form?

An expression for a quantity $f(n)$ is in closed form if we can compute it using at most a fixed number of "well known" standard operations, independent of $n$.

简单来说就是通解.

依据递推式列举了前几项后，我们猜测 $T_n = 2^n - 1$. 接下来用归纳法证明就行了.

---

其实也可以通过变换来找到通解：

Add 1 to both sides of the equations:

$T_0 + 1 = 1$;
$T_n + 1 = 2T_{n-1} + 2$, for $n > 0$.

这样的话关系就不难看出了.

The Josephus Problem

我们设 $n$ 个人形成的环最终幸存者的编号为 $J(n)$, 游戏规则是每数到第 2 个人就令其自杀.

不难发现如果 $n$ 为偶数，则游戏进行一圈后会除掉所有偶数编号的人，只留下奇数编号，且会回到起点 1 号。这就相当于让这 $n / 2$ 个人重新开始游戏，而每个人的编号除以 2 并向上取整.

这样我们就成功缩减了问题的规模:

$J(2n) = 2J(n) - 1$, for $n \geq 1$.

对于奇数个的情况，用同样的方法可以得到:

$J(2n+1) = 2J(n) + 1$, for $n \geq 1$.

再加上 base case, 则我们又得到了一个递归:

$J(1) = 1$;
$J(2n) = 2J(n) - 1$, for $n \geq 1$;
$J(2n+1) = 2J(n) + 1$, for $n \geq 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

Let $n = 2^m + l$, and we get:

$J(2^m + l) = 2l + 1$, for $m \geq 0$ and $0 \leq l < 2^m$.

显而易见，只要 $n$ 是 2 的幂，则 $J(n) = 1$. 对于一般情况 where $n = 2^m + l$, 经过 $l$ 个步骤后 $n$ 变为 2 的幂，并且此时游戏停留在编号为 $2l + 1$ 的人身上。所以这个 closed form 就得证了，即使不使用归纳法.

---

"2 的幂" 又让我们联想到了二进制，其每一位数都代表了 2 的幂的个数.

我们将 n 写成二进制，得到 $n = (b_m b_{m-1}...b_1 b_0)_2$, 且令 $b_m = 1$, 即忽略 leading 0. 则可以得到:

$n = (1 b_{m-1}b_{m-2}...b_1 b_0)_2$, ($b_m = 1$),
$l = (0 b_{m-1} b_{m-2}...b_1 b_0)_2$,
$2l = (b_{m-1} b_{m-2}...b_1 b_0 0)_2$,
$2l + 1 = (b_{m-1} b_{m-2}...b_1 b_0 1)_2$,
$J(n) = (b_{m-1} b_{m-2}...b_1 b_0 b_m)_2$, ($b_m = 1$).

我们惊奇地发现 $J(n)$ 的结果就是将 $n$ 的二进制最高位挪到最低位.

Generalization

现在我们可以思考如何求解更加一般形式的递归。比如，将 The Josephus Problem 的递归形式改写成:

$f(1) = \alpha$;
$f(2n) = 2f(n) + \beta$, for $n \geq 1$;
$f(2n+1) = 2f(n) + \gamma$, for $n \geq 1$.

我们列举出前几项的结果:

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

将 $f(n)$ 改写成:

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

同样令 $n = 2^m + l$ and $0 \leq l < 2^m$, for $n \geq 1$, 可以猜测:

$A(n) = 2^m$;
$B(n) = 2^m - 1 - l$;
$C(n) = l$.

---

为了证明 $A(n)$, $B(n)$, $C(n)$ 的表达式，我们可以采用 repertoire method:

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.

首先，我们令 $\alpha = 1$, $\beta = \gamma = 0$, 则 $f(n) = A(n)$. 该递归变为:

$A(1) = 1$;
$A(2n) = 2A(n)$, for $n \geq 1$;
$A(2n+1) = 2A(n)$, for $n \geq 1$.

很容易得到 $A(2^m + l) = 2^m$.

接着，将 $f(n) = 1$ 代入递归表达式中得到:

$1 = \alpha$;
$1 = 2\cdot1 + \beta$;
$1 = 2\cdot1 + \gamma$.

解得 $(\alpha, \beta, \gamma) = (1, -1, -1)$. 将此结果代入 $f(n)$ 表达式得:

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

最后，将 $f(n) = n$ 代入递归表达式得:

$1 = \alpha$;
$2n = 2\cdot n + \beta$;
$2n + 1 = 2\cdot n + \gamma$.

解得 $(\alpha, \beta, \gamma) = (1, 0, 1)$. 将此结果代入 $f(n)$ 表达式得:

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

至此，我们已经收集到了充足的武器库:

$A(n) = 2^m$, where $n = 2^m + 1$ and $0 \leq l < 2^m$;
$A(n) - B(n) - C(n) = 1$;
$A(n) + C(n) = n$.

由此，$A(n)$, $B(n)$, $C(n)$ 的表达式可以轻松得证.

---

那么之前的二进制解法在这个 general case 下是否还适用呢？

事实上，我们可以将这个 general recurrence 改写为:

Let $\beta_0 = \beta$ and $\beta_1 = \gamma$,

$f(1) = \alpha$;
$f(2n + j) = 2f(n) + \beta_j$, for $j = 0, 1$ and $n \geq 1$.

同样设 $n = (b_m b_{m-1}...b_1 b_0)_2$, 则有

\begin{align}f((b_m b_{m-1}...b_1 b_0)_2) &= 2f((b_m b_{m-1}...b_1)_2) + \beta_{b_0} \\ &= 4f((b_m b_{m-1}...b_2)_2) + 2\beta_{b_1} + \beta_{b_0} \\ &\vdots \\ &= 2^m f((b_m)_2) + 2^{m-1}\beta_{b_{m-1}} + \cdots + 2\beta_{b_1} + \beta_{b_0} \\ &= 2^m \alpha + 2^{m-1}\beta_{b_{m-1}} + \cdots + 2\beta_{b_1} + \beta_{b_0} \\ &= (\alpha \beta_{b_{m-1}} \beta_{b_{m-2}} \cdots \beta_{b_1} \beta_{b_0})_2 \end{align}

其中，$\alpha$ 与 $\beta$ 取值不局限于 $0$ 和 $1$.

---

如果想要进一步 generalize, 则可以考虑递归:

$f(j) = \alpha_j$, for $1 \leq j < d$;
$f(dn + j) = cf(n) + \beta_j$, for $0 \leq j < d$ and $n \geq 1$.

同样的办法，我们可以找出解:

$f((b_m b_{m-1} ... b_1 b_0)_d) = (\alpha_{b_m} \beta_{b_{m-1}} \beta_{b_{m-2}} ... \beta_{b_1} \beta_{b_0})_c$.

纯看书感觉看懂了 70%，整理了一下感觉看懂了 90%

两边同时 +1
高中的讲法是这种数列两边加上 lambda, 使得 T_n + lambda 成为等比数列，求解出 lambda 的值

按大一线性代数的看法就是 [T_n, 1]^T = A [T_{n-1}, 1]^T, A = [2, 1\newline 0, 1]
求解特征值问题得到 A = P^{-1} \Lambda P, 从而解出 T_n

查下 master theorem，公公又式式