约瑟夫环推广

上一节课说到，约瑟夫环问题的解是
<!–swig0–>
其中$n = {2^m} + l$
将$n$写成二进制可以发现，$f(n)$就是$n$的二进制循环左移1位。
现在做一下推广，求解如下递推式：
<!–swig5–>
可以设
<!–swig6–>
同样，令$n = {2^m} + l$
可以解出
<!–swig8–>
再从二进制角度理解一下，将递推式继续推广：
<!–swig9–>
可以得到解为
<!–swig10–>

递推式求和

求解如下递推式：
<!–swig11–>
用成套方法求解，设
<!–swig12–>
首先令${R_n} = 1$，可以得到$\alpha = 1,\beta = 0,\gamma = 0$，所以$A(n) = 1$。
再令${R_n} = n$，可以得到$\alpha = 0,\beta = 0,\gamma = 1$，所以$C(n) = n$。
最后令${R_n} = {n^2}$，可以得到$\alpha = 0,\beta = 2,\gamma = - 1$，所以$2B(n) - C(n) = {n^2}$，所以$B(n) = ({n^2} + n)/2$

再来一个更复杂的递推式：
<!–swig23–>
同样的方法，设
<!–swig24–>
首先令${R_n} = 1$，可以得到$\alpha = 1,\beta = 0,\gamma = -1$，所以$A(n) - C(n) = 1$。
再令${R_n} = n$，可以得到$\alpha = 0,\beta = -1,\gamma = 2$，所以$2C(n) - B(n) = n$。
这时候能不能令${R_n} = {n^2}$呢？答案是不能，因为如果${R_n} = {n^2}$，那么
<!–swig33–>显然不可能成立。
观察系数，可以令${R_n} = 2^n$，可以得到$\alpha = 1,\beta = 0,\gamma = 0$，所以$A(n) = 2^n$。
所以
<!–swig37–>