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
    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...2011-12-05
  • 0
    Also, the formula is supposed to be $$x^p=\sum\limits_{j=0}^p \left\{p\atop j\right\}x^{(j)}$$...2011-12-05
  • 0
    So would it be that $\sum_{k=0}^n k^p = \sum_{k=0}^n \sum_{j=0}^p \{$${p\j}$$\}x^{(j)}$?2011-12-05
  • 0
    Then you can try swapping summation order... :)2011-12-05
  • 0
    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?2011-12-05
  • 0
    I'm not sure why the lower argument of your Stirling subset number is suddenly different...2011-12-05
  • 0
    Oh I'm sorry I mistyped! But beyond that {p,k} should be {p,j}, the rest is correct? Is this the simplest I can write it?2011-12-05
  • 0
    Wait... why do you still have an $x$ on the right hand side? Why not $k$? Also, do you know the relationship between factorial powers and binomial coefficients?2011-12-05
  • 0
    So it's $k^{(j)}$, I'm sorry for so many typos, I copied and pasted from my original comment. Do you mean the relationship: (n choose k) = n!/(n-k)!k!?2011-12-05
  • 0
    No, I mean you're supposed to know that there's a relationship between $k^{(j)}$ and $\binom{k}{j}$...2011-12-05
  • 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...