【具体数学】递归式2

具体数学学习笔记 2

成套方法

1 约瑟夫环

$n$ 个人围成一圈，顺时针标号为 $1$ 之 $n$ 从第一个人开始，每隔一个人就杀一个人，问剩下的最后一个人是几号？

2 初次尝试

我们设 $J_n$ 为答案。

模拟一遍，拿到一份表。

$n$	$J_n$
$1$	$1$
$2$	$1$
$3$	$3$
$4$	$1$
$5$	$3$
$6$	$5$

很难看出什么性质，所以考虑别的方法。

3 模拟过程

现在试求一下 $J_{2n}$

这是刚开始剩下的：

$$1,2,3,\dots,2n-1,2n$$

进行完一轮：

$$1,3,5,7,\dots,2n-1$$

还是不太直观。

再进行一次变换

$$2 \times 1-1,2 \times 2 -1 \dots 2n-1$$

这就变成了 $J_n$ 的情形，每个点的标号都变成了原编号的两倍减一。

所以 $J_{2n}= 2 J_n -1$

考虑 $J_{2n+1}$。

这是刚开始剩下的：

$$1,2,3,\dots,2n-1,2n，2n+1$$

进行完一轮：

$$1,3,5,7,\dots,2n-1,2n+1$$

这也不是 $n$ 个啊？

那就在进行一次：

$$3,5,7,\dots,2n-1,2n+1$$

变换一下:

$$2\times 1 +1 , 2 \times 2+1 , \dots,2n+1$$

这就变成了 $J_n$ 的情形，每个点的标号都变成了原编号的两倍加一。

所以 $J_{2n+1}=2 J_n+1$

所以总式子就先列在这了：

$$J_n=1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ , n=1$$

$$J_{2n}=2J_n - 1 \ \ \ \ \ \ \ \ , n \ge 1$$

$$J_{2n+1}=2J_n + 1 \ \ \ \ \ \ \ \ , n \ge 1$$

4 寻找规律

化简不太好办。

还是先带入一下，看看结果。

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

直觉上，感觉根 $2$ 的幂有点关系。

将表拆开：

$n$	$J_n$
$1$	$1$

$n$	$J_n$
$2$	$1$
$3$	$3$

$n$	$J_n$
$4$	$1$
$5$	$3$
$6$	$5$
$7$	$7$

$n$	$J_n$
$8$	$1$
$9$	$3$
$10$	$5$
$11$	$7$
$12$	$9$
$13$	$11$
$14$	$13$
$15$	$15$

很难不注意到一个结论，但不太好表述。

若 $n=2^m+l,\ \ \ \ \ 0 \le l < 2^m$，

则 $J_n=2l+1$

5 数归证明

这个结论可以拿归纳法证明。

我们对 $m$ 进行归纳。

首先, $m=0$ 时， $J_1=1$ 成立。

现在。对于 $n=2^m+l$。

设它对 $m-1$ 成立。

如果 $l$ 为偶数：

$$J_{2^m+l}=2 J_{2^{m-1}+\frac{l}{2}}-1=2 \times (2 \times \frac{l}{2} + 1)-1 = 2l+1$$

如果 $l$ 为奇数：

$$J_{2^m+l} = 2 J_{2^{m-1}+\frac{l-1}{2}}+1=2 \times (2 \times \frac{l-1}{2} + 1) + 1 = 2l + 1$$

证毕。

---

实则，这组式子

$$J_n=1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ , n=1$$

$$J_{2n}=2J_n - 1 \ \ \ \ \ \ \ \ , n \ge 1$$

$$J_{2n+1}=2J_n + 1 \ \ \ \ \ \ \ \ , n \ge 1$$

由另一重意思

$$J_{2n+1}-J_{2n}=2$$

拿这个也可以证。

6 循环位移

还有一个有趣的结论：

$J_n$ 等于 $n$ 在二进制下循环左移一位的值。

很好理解对吧。

不严谨证明：

设 $n=2^m+l,0 \le l < 2^m$。

$$n=(b_mb_{m-1}b_{m-2}\dots b_1b_0)_2$$

$$l=(b_{m-1}b_{m-2}\dots b_1b_0)_2$$

且 $b_m=1$。

循环左移后，有

$$(b_{m-1}b_{m-2}\dots b_1b_0b_m)_2=2l+1=J_n$$

证毕。

7 成套方法

7.1 初步推广

现在，考虑这么一种式子。

$$f(1)=a$$

$$f(2n)=2f(n)+b \ \ \ \ \ \ \ \ ,n \ge 1$$

$$f(2n+1)=2f(n)+c, \ \ \ \ \ \ \ \ ,n \ge 1$$

这个递归式的解应该为

$$f(n)=A(n)a+B(n)b+C(n)c$$

7.2 特解代入

7.2.1 参数特解

我们考虑这个怎么求。

先令 $a=1,b=0,c=0$。

拿到

$$f(1)=1$$

$$f(2n)=2A(n) \ \ \ \ \ \ \ \ ,n \ge 1$$

$$f(2n+1)=2A(n), \ \ \ \ \ \ \ \ ,n \ge 1$$

不难发现

$$A(2^m+l)=2^m$$

求出了这个。

7.2.2 函数特解

接下来还有两种特解，但与上者不同，我们设出 $f$，求 $A,B,C$.

第一种

令 $f(n)=n$

易得

$$a=1$$

$$2n=2n + b$$

$$2n+1 = 2n + c$$

所以 $a=1,b=0,c=1$

将 $(a,b,c)=(1,0,1)$ 代入，拿到一个等式。

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

第二种

令 $f(n)=1$

易得

$$a=1$$

$$1 = 2 + b$$

$$1 = 2 + c$$

所以 $a=1,b=-1,c=-1$

将 $(a,b,c)=(1,-1,-1)$ 代入，拿到一个等式。

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

7.3 联立特解

令 $n=2^m+l$。

现在，有三个等式

$$A(2^m+l)=2^m$$

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

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

联立后，解得

$$A(2^m+l)=2^m$$

$$B(2^m+l)=2^m-l-1$$

$$C(2^m+l)=l$$

所以

$$f(n)=2^m a + (2^m-l-1) b + lc$$

7.4 回归问题

回到约瑟夫环。

我们将 $a=1,b=-1,c=1$ 代入，有

$$f(n)= 2^m - 2^m + l + 1 + l = 2l+1$$

很符合我们刚开始的结果。

7.5 总结

这就是成套方法，我学了一个下午才刚刚懂一点。

总体步骤：

• 找一组已知其解的特殊参数，解出特解。
• 有几个独立的参数找几组特解
• 将特解合在一块得到一般情形。

8 再谈移位

我们之前提到过

$$J_{(b_mb_{m-1}\dots b_2b_1b_0)_2}=(b_{m-1}\dots b_2b_1b_0b_m)_2$$

那推广后的式子能不能找到类似性质呢？

令 $b_0=b,b_1=c$，

则

$$f((d_md_{m-1}\dots d_2d_1b_0)_2)=2f((d_md_{m-1}\dots d_2d_1)_2)+b_{d_0}=4f(d_md_{m-1}\dots d_2)_2)+2b_{d_1}+b_{d_0}=\dots=(ab_{d_{m-1}}b_{d_{m-2}}\dots b_{d_{2}}b_{d_{1}}b_{d_{0}})_2$$

9 最后推广

我们继续研究更一般化的问题。

对于一个递归式

$$g(j)=a_j,1 \le j < d$$

$$g(nd+j)=cg(n)+b_j,n \ge 1,0 \le j < d$$

我们进行展开，最后能得到一个结论。

$$g((d_md_{m-1}\dots d_2d_1b_0)_d)=(ab_{d_{m-1}}b_{d_{m-2}}\dots b_{d_{2}}b_{d_{1}}b_{d_{0}})_c$$

对 $n$ 进行归纳易证。