具体数学-第2课（成套方法求解递归式）
原文链接：
具体数学-第2课 - WeiYang Blog今天主要讲了关于递推式和求和的一些方法，主要是成套方法。
约瑟夫环推广
上一节课说到，约瑟夫环问题的解是
其中
将 写成二进制可以发现，
就是
的二进制循环左移1位。
现在做一下推广，求解如下递推式：
可以设
同样，令
可以解出
再从二进制角度理解一下，将递推式继续推广：
可以得到解为
递推式求和
求解如下递推式：
用成套方法求解，设
首先令 ，可以得到
，所以
。
再令 ，可以得到
，所以
。
最后令 ，可以得到
，所以
，所以
再来一个更复杂的递推式：
同样的方法，设
首先令 ，可以得到
，所以
。
再令 ，可以得到
，所以
。
这时候能不能令 呢？答案是不能，因为如果
，那么
显然不可能成立。
观察系数，可以令 ，可以得到
，所以
。
所以
算法码上来 文章被收录于专栏
公众号「算法码上来」。godweiyang带你学习算法，不管是编程算法，还是深度学习、自然语言处理算法都一网打尽，更有各种计算机新鲜知识和你分享。别急，算法码上来。
