第 1 章：递归问题

河内塔问题

有 $3$ 根柱子和 $n$ 个圆盘，我们可以把最顶上的圆盘移到另外的柱子上，但不可以把大的圆盘放在小的圆盘上面

问，最少需要多少步才能把所有圆盘从一根柱子移到另外一跟柱子上

我们先命名一个状态 $T_{n}$ 表示圆盘从一根柱子移动到另外一根柱子的最少次数

那么我们思考一种移动方案，假设我们要把圆盘从 $A$ 柱移动到 $B$ 柱上

那么我们可以将 $n - 1$ 个圆盘移动 $C$ 柱上然后把最下面的圆盘移动到 $B$ 柱上，最后把 $n - 1$ 个圆盘从 $C$ 柱移到 $B$ 柱，所以，我们能得到方程

\begin{aligned} T = 1 \\ T_{n} = 2 T_{n - 1} + 1 (n > 0) \end{aligned}

我们想要得到通项公式，可以盲猜结论 $T_{n} = 2^{n} - 1, n \geq 0$

可以用数学归纳法证明

$n = 1$ 时等式成立
$n \geq 1$ 时，假设 $T_{n - 1} = 2^{n - 1} - 1$ 成立，可得

T_{n} = 2 T_{n - 1} + 1 = 2 \times (2^{n - 1} - 1) + 1 = 2^{n} - 1

证毕

平面上的直线

平面上 $n$ 条直线所界定的区域最大个数 $L_{n}$ 是多少

我们考虑假设已经有 $n - 1$ 条直线，我们需要画一条直线，这条直线最多和 $n - 1$ 条直线相交产生 $n$ 个新的区域

所以我们得到了

\begin{aligned} L_{0} = 1 \\ L_{n} = L_{n - 1} + n (n > 0) \end{aligned}

很容易我们可以得出 $L_{n} = \frac{n (n + 1)}{2} + 1, n \geq 0$

考虑一个变形，平面上由 $n$ 条这样的折线所界定区域的最大的个数 $Z_{n}$ 是多少

考虑一个折线可以看作两条直线擦掉一半，对于每个折线，我们都失去了 $2$ 块区域

所以

\begin{aligned} Z_{n} & = L_{2 n} - 2 n \\ = \frac{2 n (2 n + 1)}{2} + 1 - 2 n \\ = 2 n^{2} - n + 1, n \geq 0 \end{aligned}

约瑟夫问题

从围成标有记号的 $1$ 到 $n$ 的 $n$ 个人开始，每隔一个删去一个人，直到有一个人幸存下来

$n = 10$ 时，消去的人时 $2, 4, 6, 8, 10, 7, 1, 9$ 最后 $5$ 幸存

我们由此能得到几个规律：

每一轮杀人，杀一半，向下取整，偶数编号的人会被杀
幸存的人，重新编号

递归表达式

每轮杀人，编号减半，那么最后肯定剩下一个人，我们能不能从第 $k$ 轮活下来的那个人的编号反推出第 $k - 1$ 轮活下来的那个人的编号呢？

设 $n$ 个人时的幸存的号码为 $J (n)$

先考虑偶数的情况，第一圈把偶数的去掉，奇数留下来，假设一开始有 $2 n$ 个人，第一轮后就是

所以我们得到了一个子问题，用递归的思想，假设子问题以及求解完成了，我们可以得到表达式 $J (2 n) = 2 J (n) - 1, n \geq 1$ ,也就是说，存活的那个人的编号是子问题的答案的编号的两倍减一

然后考虑奇数，对于 $2 n + 1$ 个人

我们得到 $J (2 n + 1) = 2 J (n) + 1$

所以我们得到了表达式

\begin{aligned} J (1) & = 1 \\ J (2 n) & = 2 J (n) - 1, n \geq 1 \\ J (2 n + 1) & = 2 J (n) + 1, n \geq 1 \end{aligned}

我们通过这个式子就可以快速得到答案了

接下来尝试把递归式子转化为非递归的形式

二进制形式性质

有了递归式，我们能做出一张表：

显然可以看出， $J (n)$ 按照 $2^{m}$ 为分段，段内为一个等差数列，于是我们能写出 $J (n)$ 的封闭形式，设 $n = 2^{m} + l$ ，则：

J (2^{m} + l) = 2 l + 1, m \geq 0, 0 \leq l < 2

我们把 $n$ 转化成二进制会发现更多规律，不妨设 $n = (b_{m} b_{m - 1} \dots b_{1} b_{0})$

由于首位字母 $b_{m}$ 必为 $1$ ，所以 $n = (1 b_{m - 1} \dots b_{1} b_{0})$ ，那么 $l = (b_{m - 1} \dots b_{1} b_{0})$

所以 $J (n) = 2 l + 1 = (b_{m - 1} b_{m - 2} \dots b_{0} 1) = (b_{m - 1} b_{m - 2} \dots b_{0} b_{m})$

用计算机程序设计的行话说就是， $n$ 向左循环移动一位就得到 $J (n)$

成套方法

我们尝试把 $J$ 函数进行拓展，有一个类似于 $J$ 的递归式，引入常数 $α$

\begin{aligned} f (1) & = α \\ f (2 n) & = 2 f (n) + β, n \geq 1 \\ f (2 n + 1) & = 2 f (n) + γ, n \geq 1 \end{aligned}

我们可以构造出如下表：

可以观察出 $α$ 的系数是不超过 $n$ 的 $2$ 的最大幂， $β$ 的系数递减 $1$ ， $γ$ 的系数递增 $1$

我们可以得到 $f (n)$ 的封闭形式：

f (n) = A (n) α + B (n) β + C (n) γ

且我们观察出

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

这里可以使用数学归纳法证明，但是也可以采用特殊值法来证明，书上把这种方法称为成套方法

由于 $A (n), B (n), C (n)$ 的关系在任何情况下都是固定的，所以理论上来说 $α, β, γ$ 可以取任意值

不妨取 $(α, β, γ) = (1, 0, 0)$ ， $f (n) = A (n)$ ，由：

\begin{aligned} f (1) & = 1 \\ f (2 n) & = 2 f (n), n \geq 1 \\ f (2 n + 1) & = 2 f (n), n \geq 1 \end{aligned}

很显然可以得到 $A (n) = f (n) = 2^{m}$

我们还可以设 $f (n) = 1$ ，有：

\begin{aligned} 1 & = α \\ 1 & = 2 \times 1 + β \\ 1 & = 2 \times 1 + γ \end{aligned}

解出来得到 $(α, β, γ) = (1, - 1, - 1)$ ，于是得到了一个关系式 $1 = A (n) - B (n) - C (n)$

然后设 $f (n) = n$ ，有：

\begin{aligned} 1 & = α \\ 2 n & = 2 n + β \\ 2 n + 1 & = 2 n + γ \end{aligned}

解出来得到 $(α, β, γ) = (1, 0, 1)$ ，于是得到了一个关系式 $n = A (n) + C (n)$

联立三个式子：

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

于是 $B (n) = 2^{m} - 1 - l, C (n) = l$ 就可以被解出来了，这就是成套方法

有多少个独立的参数，我们就需要多少个特殊的值，本题中有三个 $(α, β, γ)$

推广的约瑟夫递归式

前面我们得到了一个二进制下循环移位的性质，那么推广的约瑟夫表达式是否也有类似的性质呢？

推广的递归式的形式如下：

\begin{aligned} f (1) & = α \\ f (2 n + j) & = 2 f (n) + β_{j}, j = 0, 1, n \geq 1 \end{aligned}

展开就是

\begin{aligned} f ((b_{m} b_{m - 1} \dots b_{0})_{2}) = & 2 f ((b_{m} b_{m - 1} \dots b_{2})_{2}) + β_{b_{0}} \\ = & 4 f ((b_{m} b_{m - 1} \dots b_{2})_{2}) + 2 β_{b_{1}} + β_{b_{0}} \\ ⋮ \\ = & 2^{m} f ((b_{m})_{2}) + 2^{m - 1} β_{b_{m - 1}} + \dots + 2 β_{b_{1}} + β_{b_{0}} \\ = & 2^{m} α + 2^{m - 1} β_{b_{m - 1}} + \dots + 2 β_{b_{1}} + β_{b_{0}} . \end{aligned}

所以我们可以解除二进制的限制，这里的 $b_{i}$ 一点是 $0, 1$ ，但 $β_{j}$ 可以不为 $0, 1$

f ((b_{m} b_{m - 1} \dots b_{1} b_{0})_{2}) = (α β_{b_{m} - 1} β_{b_{m - 2}} \dots β_{b_{1}} β_{b_{0}})_{2} .

我们把上面的表格换一种形式就可以看出

完全符合上面的形式，这里的 $β = β_{0}, α = γ$

于是，我们可以考虑推广基数，这里我们设基数为 $d$

\begin{aligned} f (j) & = α_{j}, 1 \leq j < d; \\ f (d n + j) & = c f (n) + β_{j}, 0 \leq j < d, n \geq 1 \end{aligned}

这个的解是：

f ((b_{m} b_{m - 1} \dots b_{1} b_{0})_{d}) = (α_{b_{m}} β_{b_{m - 1}} β_{b_{m - 2}} \dots β_{b_{1}} β_{b_{0}})_{c}

例如，我们有递归式：

\begin{aligned} f (1) & = 34; \\ f (2) & = 5; \\ f (3 n) & = 10 f (n) + 76, n \geq 1; \\ f (3 n + 1) & = 10 f (n) - 2, n \geq 1; \\ f (3 n + 2) & = 10 f (n) + 8, n \geq 1; \end{aligned}

假设我们这里要计算 $f (19)$ ，有 $d = 3$ ， $c = 10$ ，我们可以把 $19$ 转化成三进制 $(201)_{3}$ ，这里的 $α_{1} = 2, β_{0} = 76, b e t a_{1} = - 2$ ，所以 $f (19) = f ((201)_{3}) = (5 76 - 2)_{10} = 500 + 760 - 2 = 1258$