具体数学-第2课（成套方法求解递归式）

原文链接：

具体数学-第2课 - WeiYang Bloggodweiyang.com

今天主要讲了关于递推式和求和的一些方法，主要是成套方法。

约瑟夫环推广

上一节课说到，约瑟夫环问题的解是

其中

将

写成二进制可以发现，

就是

的二进制循环左移1位。 现在做一下推广，求解如下递推式：

可以设

同样，令

可以解出

再从二进制角度理解一下，将递推式继续推广：

可以得到解为

递推式求和

求解如下递推式：

用成套方法求解，设

首先令

，可以得到

，所以

。 再令

，可以得到

，所以

。 最后令

，可以得到

，所以

，所以

再来一个更复杂的递推式：

同样的方法，设

首先令

，可以得到

，所以

。 再令

，可以得到

，所以

。 这时候能不能令

呢？答案是不能，因为如果

，那么

显然不可能成立。 观察系数，可以令

，可以得到

，所以

。 所以