zsh

Formulas

$$\begin{cases} J(1)&=1 \\ J(2n)&=2J(n)-1 \\ J(2n+1)&=2J(n)+1 \tag{1.8} \end{cases}$$ $$J(2^m+l)=2l+1, m\ge0, 0\le l\lt 2^m \tag{1.9}$$ $$J((b_m b_{m-1}\cdots b_1 b_0)_2) = (b_{m-1}\cdots b_1 b_0 b_m)_2 \tag{1.10}$$ $$\begin{cases} f(1)&=\alpha \\ f(2n)&=2f(n)+\beta \\ f(2n+1)&=2f(n)+\gamma \tag{1.11} \end{cases}$$

$$f(n) = A(n)\alpha + B(n)\beta + C(n)\gamma \tag{1.13}$$ $$\begin{cases} A(n)&=2^m \\ B(n)&=2^m-1-l \\ C(n)&=l \tag{1.14} \end{cases}$$ $$\begin{cases} f(1)&=\alpha \\ f(2n+j) &= 2f(n)+\beta_j, \quad j=0,1, \quad n\ge1 \tag{1.15} \end{cases}$$ $$f((b_m b_{m-1} \cdots b_1 b_0)_2) = (\alpha \beta_{b_{m-1}} \beta_{b_{m-2}} \cdots \beta_{b_1} \beta_{b_0})_2 \tag{1.16}$$ $$\begin{cases} f(j) &= \alpha_j, \quad 1\le j \lt d; \\ f(dn+j) &= cf(n)+\beta_j \tag{1.17} \end{cases}$$ $$f((b_m b_{m-1} \cdots b_1 b_0)_d) = (\alpha_{b_m} \beta_{b_{m-1}} \beta_{b_{m-2}} \cdots \beta_{b_1} \beta_{b_0})_c \tag{1.18}$$

约瑟夫环问题

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

求通解

令$J(n)$为n个人的约瑟夫环，最后留下来的人。
容易得到递推关系式(1.8)

根据前面几个J(n)，列表：

猜想有通解(1.9)，并且可以通过数学归纳法证明之。

将n用二进制展开，有：

于是得到公式(1.10)

至此，已经解出了原始约瑟夫环问题的通解。

一般化

将(1.8)的递推表达式，一般化到(1.11)
列举前几个f(n)的值：得到表(1.12)

可以根据规律推测有通解(1.13)，并且可以推测出通解值为(1.14)+归纳法证明之。

这里书中提供了另外一种方法来求得(1.14)的值——成套方法。

$$\begin{cases} \alpha=1, \beta=\gamma=0 &\Rightarrow A(n)=2^m, 其中n=2^m+l, 0\le 1 \lt 2^m \\ f(n)=1 &\Rightarrow A(n)-B(n)-C(n)=1 \\ f(n)=n &\Rightarrow A(n)+C(n) = n \end{cases}$$

进而可以解得(1.14)

推广

令(1.11)中的$\beta_0=\beta, \quad \beta_1=\gamma$, 可以得到化为(1.15)
随之可以得到(1.16)：左值根据(1.15)逐层展开m次得到右值。

再次推广，得到问题(1.17)，其解为(1.18)

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。