首先我们从(n)个整数的平方和开始，也就是求
[S(n)=sumlimits_{i=1}^ni^2
]
我们可以尝试对(S(n))进行扰动，就有
[egin{align}S(n)&=sumlimits_{i=1}^n(i+1)^2-(n+1)^2+1
onumber\&=sumlimits_{i=1}^n(i^2+2i+1)-(n+1)^2+1
onumber\&=S(n)+2sumlimits_{i=1}^ni-n(n+1)
onumberend{align}
]
然后我们发现扰动失败了，(S(n))被消掉了，但是我们意外发现了求(sumlimits_{i=1}^ni)的公式
于是我们猜测一下，是否可以用更高级的幂和(C(n)=sumlimits_{i=1}^ni^3)来求出(S(n))
[egin{align}C(n)&=sumlimits_{i=1}^n(i+1)^3-(n+1)^3+1
onumber\&=sumlimits_{i=1}^n(i^3+3i^2+3i+1)-(n+1)^3+1
onumber\&=C(n)+3S(n)+dfrac{3n(n+1)}{2}-n(n+1)(n+2)
onumber\Longrightarrow S(n)&=dfrac{n(n+1)(n+2)-frac{3n(n+1)}{2}}{3}
onumber\&=dfrac{n(n+1)(2n+1)}{6}
onumberend{align}
]
于是这样我们得到了(S(n))的公式，既然如此，我们可以尝试着计算更高阶的幂和，我们设(S_k(n)=sumlimits_{i=1}^ni^k)，那么有
[egin{align}S_k(n)&=sumlimits_{i=1}^ni^k=sumlimits_{i=1}^n(i+1)^k-(n+1)^k+1
onumber\&=sumlimits_{i=1}^nsumlimits_{j=0}^kinom{k}{j}i^j-(n+1)^k+1
onumber\&=sumlimits_{j=0}^kinom{k}{j}S_j(n)-(n+1)^k+1
onumberend{align}
]
这样就有
[S_{k-1}(n)=dfrac{(n+1)^k-sumlimits_{j=0}^{k-2}inom{k}{j}S_j(n)-1}{k}
]
或者可以写成
[S_k(n)=dfrac{(n+1)^{k+1}-sumlimits_{j=0}^{k-1}inom{k+1}{j}S_j(n)-1}{k+1}
]
那么我们就可以在(O(k^2))的时间内计算(S_k(n))了
其实我们可以在(O(k))的时间内求出(S_k(n))，具体可见浅谈算法——拉格朗日插值