前言
计算(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}
]