(i^2)求和
老祖宗告诉我们(sum_{i=1}^n i^2 = frac{n(n 1)(2n 1)}{6})
但是这玩意儿是怎么出来的呢？感觉网上用立方差证明的思路太low了，今天偶然间在Miskcoo大佬的博客中看到了一种脑洞清奇通俗易懂的证明方法
我们要求的是(S_n = sum_{i=1}^n i^2)，现在我们对(C_n = sum_{i=1}^n i^3)来进行"扰动"。
首先列一个恒等式
[sum_{i=1}^{n 1} i^3 = C_n (n 1)^3]
这里有个骚操作是把前面的转化一下
[sum_{i=0}^n (i 1)^3 = C_n (n 1)^3]
然后就可以推柿子啦。
[ begin{aligned} sum_{i=0}^n i^3 3i^2 3i 1 &= C_n (n 1)^3\ C_n 3S_n 3frac{n(n 1)}{2} (n 1)&= C_n (n 1)^3\ end{aligned} ]
[ begin{aligned} Rightarrow S_n &= frac{2(n 1)^3 - 3n(n 1)-2(n 1)}{6}\ &=frac{n(2n 1)(n 1)}{6} end{aligned} ]
同时这个方法具有非常强的扩展性，我们也可以推导出(i^k)的公式，但是计算起来的复杂度却是(k^2)的，感觉还是拉格朗日插值(k log k)好用一些
参考资料
幂和
