前言

计算(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=5sum_{k=1}^nk^4+10sum_{k=1}^nk^3+10sum_{k=1}^nk^2+5sum_{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}
]