MENU

扰动法学习笔记

扰动法可以帮助我们用封闭形式来求解一个和式。

个人感觉扰动法还是比较套路的。

具体来说,如果我们有这样一个和式 $S_k=\sum_{i=0}^kf(i)$,我们对其进行扰动,抽出第一项和最后一项
$$
\begin{aligned}
S_k&=\sum\limits_{i=0}^kf(i) \\
S_k+f(k+1)&=\sum\limits_{i=0}^{k+1}f(i) \\
S_k+f(k+1)&=\sum\limits_{i=0}^{k}f(i+1)+f(0)
\end{aligned}
$$
然后再想办法对后面进行化简即可,通常 $\sum_{i=0}^kf(i+1)$ 可以再拆开被表示为含 $S_k$ 的多项式,这样我们就得到了一个方程,从而能够解得 $S_k$ 的封闭形式。

实际上只需要几个例子,你就能够很好地运用扰动法了。

首先是非常常见的几何级数 $S_k=\sum_{i=0}^kax^i$,对其进行扰动
$$
\begin{aligned}
S_k&=\sum\limits_{i=0}^kax^i \\
S_k+ax^{k+1}&=\sum\limits_{i=0}^{k+1}ax^i \\
S_k+ax^{k+1}&=\sum\limits_{i=0}^kax^{i+1}+a \\
S_k+ax^{k+1}&=xS_k+a \\
(x-1)S_k&=ax^{k+1}-a \\
S_k&=\frac{ax^{k+1}-a}{x-1}(x\ne1)
\end{aligned}
$$
你其实会发现扰动法几乎不需要怎么动脑子 /fad

接下来考虑一个稍微复杂一点的和式,平方和 $S_k=\sum_{i=1}^ki^2$,我们仍然尝试着把扰动法往上套
$$
\begin{aligned}
S_k&=\sum\limits_{i=1}^ki^2 \\
S_k+(k+1)^2&=\sum\limits_{i=1}^k(i+1)^2+1 \\
S_k+k^2+2k+1&=\sum\limits_{i=1}^k(i^2+2i+1)+1 \\
S_k+k^2+2k+1&=S_k+2\sum\limits_{i=1}^ki+k+1
\end{aligned}
$$
然后你发现 $S_k$ 居然被抵消了。

但是你可以发现另外一件奇妙的事情,我们把式子继续往下推
$$
\begin{aligned}
2\sum\limits_{i=1}^ki&=k^2+k \\
\sum\limits_{i=1}^ki&=\frac{k^2+k}{2}
\end{aligned}
$$
我们实际上可以借助这个式子得到等差数列的求和公式,那么, 为了处理平方和,我们可以尝试着去对立方和进行扰动。
$$
\begin{aligned}
S_k&=\sum\limits_{i=1}^ki^3 \\
S_k+(k+1)^3&=\sum\limits_{i=1}^k(i+1)^3+1 \\
S_k+k^3+3k^2+3k+1&=\sum\limits_{i=1}^{k}(i^3+3i^2+3i+1)+1 \\
S_k+k^3+3k^2+3k+1&=S_k+3\sum\limits_{i=1}^{k}i^2+3\sum\limits_{i=1}^ki+k+1 \\
3\sum\limits_{i=1}^ki^2&=k^3+3k^2+2k-3\sum\limits_{i=1}^ki \\
3\sum\limits_{i=1}^ki^2&=k^3+3k^2+2k-\frac{3k^2+3k}{2} \\
\sum\limits_{i=1}^ki^2&=\frac{2k^3+6k^2+4k-3k^2-3k}{6} \\
\sum\limits_{i=1}^ki^2&=\frac{2k^3+3k^2+k}{6}
\end{aligned}
$$
我们得到了我们想要的结果,可以验证,最后的封闭形式就是我们所熟知的平方和求和公式
$$
\sum\limits_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6}
$$
接下来,考虑如何去处理自然数幂之和 $S_{k}=\sum_{i=1}^ni^k$,这个式子已经较上面发生了很大改变
$$
\begin{aligned}
S_k&=\sum\limits_{i=1}^ni^k \\
S_k+(n+1)^k&=\sum\limits_{i=1}^n(i+1)^k+1 \\
S_k&=\sum\limits_{i=1}^n(i+1)^k-(n+1)^k+1
\end{aligned}
$$
这个式子变得有些麻烦,直接用二项式定理强行展开
$$
\begin{aligned}
S_k&=\sum\limits_{i=1}^n\sum\limits_{j=0}^k\binom{k}{j}i^j-(n+1)^k+1 \\
S_k&=\sum\limits_{j=0}^k\binom{k}{j}\sum\limits_{i=1}^ni^j-(n+1)^k+1 \\
S_k&=\sum\limits_{j=0}^k\binom{k}{j}S_j-(n+1)^k+1 \\
S_k&=\sum\limits_{j=0}^{k-1}\binom{k}{j}S_j-(n+1)^k+1+S_k \\
0&=\sum\limits_{j=0}^{k-1}\binom{k}{j}S_j-(n+1)^k+1 \\
0&=\sum\limits_{j=0}^{k-2}\binom{k}{j}S_j-(n+1)^k+1+kS_{k-1} \\
kS_{k-1}&=(n+1)^k-\sum\limits_{j=0}^{k-2}\binom{k}{j}S_j-1 \\
S_{k-1}&=\frac{(n+1)^k-\sum\limits_{j=0}^{k-2}\binom{k}{j}S_j-1}{k}
\end{aligned}
$$
令 $k\leftarrow k+1$
$$
S_k=\frac{(n+1)^{k+1}-\sum\limits_{j=1}^{k-1}\binom{k+1}{j}S_j-1}{k+1}
$$
这样可以得到自然数幂之和的计算方式,当然这并不是通项,而是一个递推式。

当然需要提到的是,从算法角度来说,计算这样一个递推式的复杂度是 $O(k^2)$ 或 $O(k^2\log k)$ 的($\log$ 决定于乘法逆元的处理方式),这个复杂度并不优秀,实际上只需要进行拉格朗日插值, 就能够在 $O(k)$ 的时间复杂度内对任意 $n,k$ 求出 $S_k$ 的值。

练手题:LuoguP4948 数列求和

Last Modified: November 5, 2022
Archives Tip
QR Code for this page
Tipping QR Code