前言

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

公式

[sum_{i=1}^ni=frac{nn+1)}{2}
]

[sum_{i=1}^ni^2=frac{nn+1)2n+1)}{6}
]

[sum_{i=1}^ni^3=frac{n^2n+1)^2}{4}
]

[sum_{i=1}^{n}i^4=frac{nn+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+5n-1)^4+10n-1)^3+10n-1)^2+5n-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{nn+1)}{2}
]

[sum_{k=1}^nk^2=frac{nn+1)2n+1)}{6}
]

[sum_{k=1}^nk^3=frac{n^2n+1)^2}{4}
]

所以

[sum_{i=1}^{n}i^4=frac{nn+1)2n+1)3n^2+3n-1)}{30}
]