具体数学内容总结——第1章 递归问题

书籍介绍：

https://book.douban.com/subject/21323941/

github仓库：

https://github.com/Doraemonzzz/Concrete-Mathematics

后续会回顾每章的重点内容，这次先回顾第1章——递归问题。

约瑟夫问题

成套方法（repertoire method）

对于形如如下问题的求解：

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

首先写成如下形式：

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

然后通过给$\alpha,\beta,\gamma$赋特殊的值，找到特殊的$f(n)$，由此得到$A(n),B(n),C(n)$的方程组，最后求解出结果。

2进制展开

考虑另一种形式的递推式

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

那么利用2进制展开可得

$$\begin{aligned} f\left(\left(b_{m} b_{m-1} \cdots b_{1} b_{0}\right)_{2}\right) =&2 f\left(\left(b_{m} b_{m-1} \cdots b_{1}\right)_{2}\right)+\beta_{b_{0}} \\ =&4 f\left(\left(b_{m} b_{m-1} \cdots b_{2}\right)_{2}\right)+2 \beta_{b_{1}}+\beta_{b_{0}} \\ &\vdots \\ =&2^{m} f\left(\left(b_{m}\right)_{2}\right)+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}}\\ =&\left(\alpha \beta_{b_{m-1}} \beta_{b_{m-2}} \cdots \beta_{b_{1}} \beta_{b_{0}}\right)_{2} \end{aligned}$$