计算\(1-n\)和的公式，想必大家都已了解，即等差数列求和公式。下面介绍一种能在\(O(1)\)时间内算出\(1-n\)四次方和的公式。二次方、三次方和的公式可类比推导。

\[\sum_{i=1}^ni=\frac{n(n+1)}{2}\]\[\sum_{i=1}^ni^2=\frac{n(n+1)(2n+1)}{6}\]\[\sum_{i=1}^ni^3=\frac{n^2(n+1)^2}{4}\]\[\sum_{i=1}^{n}i^4=\frac{n(n+1)(2n+1)(3n^2+3n-1)}{30}\]

假设我们已知\(\sum_{i=1}^{n}i\)，\(\sum_{i=1}^{n}i^2\)，\(\sum_{i=1}^{n}i^3\)的公式。

\(n^5\)

\(=((n-1)+1)^5\)

\(=C_5^0*n^5+C_5^1*n^4+C_5^2*n^3+C_5^3*n^2+C_5^4*n^1+C_5^5*n^0\)

\(=(n-1)^5+5(n-1)^4+10(n-1)^3+10(n-1)^2+5(n-1)+1\)

记上式为\(1\)式。\(2\)到\((n-1)\)式以此类推。

\(2^5=1^5+5*1^4+10*1^3+10*1^2+5*1+1\)

上式为\(n\)式。

将\(1\)到\(n\)式全部相加，得\[(n+1)^5-1^5=5\sum_{k=1}^nk^4+10\sum_{k=1}^nk^3+10\sum_{k=1}^nk^2+5\sum_{k=1}^nk+n\] 又因为\[\sum_{k=1}^nk=\frac{n(n+1)}{2}\]\[\sum_{k=1}^nk^2=\frac{n(n+1)(2n+1)}{6}\]\[\sum_{k=1}^nk^3=\frac{n^2(n+1)^2}{4}\] 所以\[\sum_{i=1}^{n}i^4=\frac{n(n+1)(2n+1)(3n^2+3n-1)}{30}\]