# Stirling Numbers of the Second Kind and Finding a General Formula

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?

-
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

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*}