16
$\begingroup$

Can someone tell me how to get a closed form for

$$\sum_{k=1}^n k^p$$

For $p = 1$, it's just the classic $\frac{n(n+1)}2$.

What is it for $p > 1$?

$\endgroup$
4

2 Answers 2

28
$\begingroup$

The general formula is fairly complicated:

$$\sum_{k=1}^n{k^x} = {1\over x+1}\sum_{k=0}^x{{x+1\choose k}B_k n^{x+1-k}}$$

Where $B_k$ are the Bernoulli numbers, discovered around the same time, but independently, by Johann Bernoulli and Seki Takakazu.

This is commonly called "Faulhaber's formula", but that is a misattribution. The Donald Knuth paper "Johann Faulhaber and sums of powers" explains the history in some detail, including what Faulhaber did and did not know. In particular, he did not know the general formula above, although he did work on many special cases.

The first few special cases are:

$$\begin{array}{ll} \sum_{k=1}^n 1 & = n \\ \sum_{k=1}^n k & = \frac12{(n^2+n)} \\ \sum_{k=1}^n k^2 & = \frac16{(2n^3+3n^2+n)} \\ \sum_{k=1}^n k^3 & = \frac14{(n^4+2n^3+n^2)} \\ \sum_{k=1}^n k^4 & = \frac1{30}{(6n^5+15n^4+10n^3-n)} \\ \sum_{k=1}^n k^5 & = \frac1{12}{(2n^6+6n^5+5n^4-n^2)} \\ \end{array}$$

$\endgroup$
2
$\begingroup$

By Binomial Series

$(n+1)^x=1 + {x \choose 1}\sum_{k=1}^n{k^{x-1}} + {x \choose 2}\sum_{k=1}^n{k^{x-2}}+{x \choose 3}\sum_{k=1}^n{{k^{x-3}}} ...+{x \choose x-1}\sum_{k=1}^n{{k^{x-x+1}}}+{x \choose x}\sum_{k=1}^n{{k^{x-x}}}$

which becomes

$(n+1)^x = 1 + {x \choose 1}\sum_{k=1}^n{k^{x-1}} + {x \choose 2}\sum_{k=1}^n{k^{x-2}}+{x \choose 3}\sum_{k=1}^n{{k^{x-3}}} ....+{x \choose x-1}\sum_{k=1}^n{{k}}+{x \choose x}\sum_{k=1}^n{{1}}$

for example consider $x=3$

$(n+1)^3 = 1 + {3 \choose 1}\sum_{k=1}^n{k^{2}} + {3 \choose 2}\sum_{k=1}^n{k^{1}}+{3 \choose 3}\sum_{k=1}^n{{1}}$

$(n+1)^3 = 1 + 3\sum_{k=1}^n{k^{2}} + 3*\frac{n*(n+1)}{2}+n$

which gives $\sum_{k=1}^n{k^2} =(1/6)*n*(n+1)*(2n+1)$

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.