扰动法学习笔记

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

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

具体来说，如果我们有这样一个和式 $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}
$$
这样可以得到自然数幂之和的计算方式，当然这并不是通项，而是一个递推式。