河内塔问题

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

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

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

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

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

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

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

可以用数学归纳法证明

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

$T_n=2T_{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 \ge0$

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

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

所以

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

约瑟夫问题

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

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

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

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

递归表达式

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

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

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

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

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

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

所以我们得到了表达式

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

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

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

二进制形式性质

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

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

$J(2^m+l)=2l+1,\ m\ge 0,\ 0\le l<2$

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

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

所以 $J(n)=2l+1=(b_{m-1}b_{m-2}\cdots b_01)=(b_{m-1}b_{m-2}\cdots b_0b_m)$

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

成套方法

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

$\begin{aligned} f(1)&=\alpha \\ f(2n)&=2f(n)+ \beta ,n\ge 1\\ f(2n+1)&=2f(n)+\gamma ,n\ge 1\\ \end{aligned}$

我们可以构造出如下表：

可以观察出 $\alpha$ 的系数是不超过 $n$ 的 $2$ 的最大幂，$\beta$ 的系数递减 $1$ ，$\gamma$ 的系数递增 $1$

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

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

且我们观察出

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

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

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

不妨取 $(\alpha,\beta,\gamma)=(1,0,0)$，$f(n)=A(n)$，由：

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

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

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

$\begin{aligned} 1&=\alpha \\ 1&=2\times 1+\beta \\ 1&=2\times1 + \gamma \end{aligned}$

解出来得到 $(\alpha,\beta,\gamma)=(1,-1,-1)$，于是得到了一个关系式 $1=A(n)-B(n)-C(n)$

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

$\begin{aligned} 1&=\alpha \\ 2n&=2n+\beta \\ 2n+1&=2n+\gamma \end{aligned}$

解出来得到 $(\alpha,\beta,\gamma)=(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$ 就可以被解出来了，这就是成套方法

有多少个独立的参数，我们就需要多少个特殊的值，本题中有三个 $(\alpha,\beta,\gamma)$

推广的约瑟夫递归式

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

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

$\begin{aligned} f(1)&=\alpha \\ f(2n+j)&=2f(n)+\beta_j\ ,\ j=0,1\ ,n\ge 1 \\ \end{aligned}$

展开就是

$\begin{aligned} f((b_m b_{m-1} \dots b_0)_2) =& 2f((b_m b_{m-1} \dots b_2)_2) + \beta_{b_0} \\ =& 4f((b_m b_{m-1} \dots 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}. \end{aligned}$

所以我们可以解除二进制的限制，这里的 $b_i$ 一点是 $0,1$ ，但 $\beta_j$ 可以不为 $0,1$

$f\left((b_m b_{m-1} \cdots b_1 b_0)_2\right) = (\alpha \beta_{b_m-1} \beta_{b_{m-2}} \cdots \beta_{b_1} \beta_{b_0})_2.$

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

完全符合上面的形式，这里的 $\beta = \beta_0, \alpha = \gamma$

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

$\begin{aligned} f(j) &= \alpha_j, \quad 1 \leq j < d; \\ f(dn + j) &= c f(n) + \beta_j, \quad 0 \leq j < d, \quad n \geq 1 \end{aligned}$

这个的解是：

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

例如，我们有递归式：

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

假设我们这里要计算 $f(19)$，有 $d=3$ ，$c=10$ ，我们可以把 $19$ 转化成三进制 $(201)_3$ ，这里的 $\alpha_1=2,\beta_0=76,beta_1=-2$，所以 $f(19)=f((201)_3)=(5\ 76\ -2)_{10}=500 + 760 - 2 = 1258$