简述
扰动法通常可以用来求柿子的递推式。柿子一般需要形如一个 \(f(k)=\sum_{i=1}^ng(k,i)\)，注意 \(k\) 不一定需要为 \(n\)。
我们有：
\[\sum_{i=1}^{n+1}g(k,i)=\sum_{i=1}^ng(k,i)+g(k,n+1)=g(k,1)+\sum_{i=2}^{n+1}g(k,i)\\
f(k)=\sum_{i=2}^{n+1}g(k,i)+g(k,1)-g(k,n+1)
\]
之后我们通常会想办法把 \(\sum_{i=2}^{n+1}\) 推出 \(\sum_{i=1}^n\) 的形式，然后再推成与 \(f\) 有关的形式，即可得到一个 \(f\) 的递推式。
例题
P4948 数列求和
我们定义：
\[f(k)=\sum_{i=1}^ni^ka^i
\]
有：
\[\sum_{i=1}^ni^ka^i+(n+1)^ka^{n+1}=a+\sum_{i=1}^n(i+1)^ka^{i+1}
\]
可得：
\[\begin{aligned}
f(k)&=(\sum_{i=1}^n(i+1)^ka^{i+1})+a-(n+1)^ka^{n+1}\\
&=(a\sum_{i=1}^n\sum_{j=0}^k\binom{k}{j}i^ja_i)+a-(n+1)^ka^{n+1}\\
&=(a\sum_{j=0}^k\binom{k}{j}f(j))+a-(n+1)^ka^{n+1}
\end{aligned}
\]
把右式中的 \(f(k)\) 移到左边，然后两侧同除系数，得到：
\[f(k)=\frac{(n+1)^ka^{n+1}-a-a\sum_{j=0}^{k-1}\binom{k}{j}f(j)}{a-1}
\]
于是即可 \(O(k^2)\) 递推。
但 \(a=1\) 怎么办？此时有：
\[(n+1)^k-1-\sum_{j=0}^{k-1}\binom{k}{j}f(j)=0\\
(n+1)^{k+1}-1-\sum_{j=0}^{k}\binom{k+1}{j}f(j)=0
\]
我们把 \(f(k)\) 移到另一边，得到：
\[f(k)=\frac{(n+1)^{k+1}-1-\sum_{j=0}^{k-1}\binom{k+1}{j}f(j)}{\binom{k+1}{k}}
\]
同样 \(O(k^2)\) 递推即可。