递归式的一般求解方法

对于一个通用的递归式模式

$$f(i)=a_i (1\le j < d); \\ f(dn+i)=cf(n)+\beta_i(0\le j < d, 1\le n)$$

我们于是可以把$n$用$d$进制表示出来

$$n = (b_mb_{m-1}...b_{1}b_{0})_d$$

然后把答案用$c$进制表示出来

$$f(n)=(a_{b_m}\beta_{b_{m - 1}}\beta_{b_{m - 2}}...\beta_{b_{1}}\beta_{b_{0}})_c$$

即：

$$f((b_mb_{m-1}...b_{1}b_{0})_d)=(a_{b_m}\beta_{b_{m - 1}}\beta_{b_{m - 2}}...\beta_{b_{1}}\beta_{b_{0}})_c$$

或者，可以把独立的系数给拆开考虑，比如变成如下形式：

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

然后根据f函数的特殊性质或者特殊的n来进行推导

参考笔记