Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I just want to know if I solved this problem correctly, thanks!

Find and verify a general formula for $\sum\limits_{k=0}^n k^p$ involving Stirling numbers of the second kind.

So I expanded $$\sum_{k=0}^n k^p = 0^p + 1^p + \cdots + n^p\tag{1}$$

and the Stirling numbers of the second kind can be represented as: $$n^p = \sum_{k=0}^n S(p,k)[n]_{k}\tag{2}$$

After replacing each term in $(1)$ by $(2)$, I should get:

$$\sum_{k=0}^n k^p = \sum_{k=0}^n S(p,k)[0]_{k} + \sum_{k=0}^n S(p,k)[1]_{k} + \cdots + \sum_{k=0}^n S(p,k)[n]_{k}\;.$$

Is this correct? How else am I supposed to verify this formula?

share|cite|improve this question
The confusion is because you're using the same index variable for the sums of powers and the expansion of the power function in terms of factorial powers. Try using different index variables... – J. M. Dec 5 '11 at 4:38
Also, the formula is supposed to be $$x^p=\sum\limits_{j=0}^p \left\{p\atop j\right\}x^{(j)}$$... – J. M. Dec 5 '11 at 4:41
So would it be that $\sum_{k=0}^n k^p = \sum_{k=0}^n \sum_{j=0}^p \{$${p\j}$$\}x^{(j)}$? – Gbean Dec 5 '11 at 5:18
Then you can try swapping summation order... :) – J. M. Dec 5 '11 at 5:28
Is $\sum_{k=0}^n k^p = \sum_{j=0}^p \sum_{k=0}^n \{p, k\}x^{(j)}$ correct? Is there a combinatorial proof for this? – Gbean Dec 5 '11 at 5:31
up vote 5 down vote accepted

I'll sketch out the solution. Some of this stuff is in Concrete Mathematics; you can look up stuff that isn't familiar there, or try to establish things on your own. Here we use $\left\{n\atop k\right\}$ for the Stirling subset number (second kind) and $x^{(j)}$ for the falling factorial.

$$\begin{align*}\sum_{k=0}^n k^p&=\sum_{k=0}^n \sum_{j=0}^p \left\{p\atop j\right\}k^{(j)}\\&=\sum_{k=0}^n \sum_{j=0}^p j!\left\{p\atop j\right\}\binom{k}{j}\\&=\sum_{j=0}^p j!\left\{p\atop j\right\}\sum_{k=0}^n \binom{k}{j}\\&=\sum_{j=0}^p j!\left\{p\atop j\right\}\binom{n+1}{j+1}\\&=\sum_{j=0}^p \frac{n+1}{j+1}j!\left\{p\atop j\right\}\binom{n}{j}\\&=(n+1)\sum_{j=0}^p \left\{p\atop j\right\}\frac{n^{(j)}}{j+1}\end{align*}$$

Actually, any of the last three expressions could be the answer...

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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