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?
Best Answer
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...