3
$\begingroup$

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?

  • 0
    $k^{(j)} = k(k-1)...(k-j+1)$?2011-12-05

1 Answers 1

6

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...