3
$\begingroup$

In Table of Integrals, Series, and Products. Seventh Edition. I.S. Gradshteyn and I.M. Ryzhik, there is 0.154.3 $$ \sum_{k=0}^N (-1)^k {N \choose k} k^{n-1} =0, N \geq n \geq 1; 0^0 ≡ 1 $$ 0.154.4 $$ \sum_{k=0}^n (-1)^k {n \choose k} k^{n} =(-1)^n n!, n \geq 0; 0^0 ≡ 1 $$

I would like to know, there is any generalization for 0.154.4 for a general, higher power of $k$? $$ \sum_{k=0}^n (-1)^k {n \choose k} k^{n+m} =?, n \geq 0; m\geq0; 0^0 ≡ 1 $$

$\endgroup$
2
  • 1
    $\begingroup$ Each of your formulas has both $N$ and $n$ in it. Is that what you mean to write? $\endgroup$ Apr 13, 2015 at 0:28
  • $\begingroup$ @GerryMyerson Thank you for pointing out. I overlooked at the symbols. Now only 0.154.3 has both $N$ and $n$. $\endgroup$
    – user26143
    Apr 13, 2015 at 0:33

3 Answers 3

8
$\begingroup$

$$ \sum_{k=0}^n (-1)^k {n \choose k} k^{n+m} = (-1)^n\cdot n!\cdot S(n+m,n), $$ where $S(\cdot,\cdot)$ is Stirling number of the second kind. This is essentially formula (10) at http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html

In particular, for $m<0$, we have $S(n+m,n)=0$; and for $m=0$, we have $S(n+m,n)=S(n,n)=1$, giving the formulae 0.154.3-4 from Gradshteyn and Ryzhik.

$\endgroup$
2
$\begingroup$

Here is one way of looking at the answer to this problem.

For any function $f: \mathbb{N} \to \mathbb{R}$, one can form the exponential generating function or formal power series $E_f(x) = \sum_{j \geq 0} \frac{f(j) x^j}{j!}$. The power series product of such egf's corresponds to the convolution product defined by

$$(f \ast g)(n) = \sum_{j+k = n} \frac{n!}{j!k!} f(j) g(k).$$

For example, if $g(k) = (-1)^k$, then $E_g(x) = \exp(-x)$, and the convolution product

$$h(n) := (f \ast g)(n) = \sum_j (-1)^{n-j} {n \choose j} f(j)$$

corresponds to the equation $E_h = E_f \cdot \exp(-x)$. Rewriting this as $E_h \exp(x) = E_f$ (and with an option to swap out other dummy variables for $j$), we arrive at a Möbius inversion formula

$$h(n) = \sum_k (-1)^{n-k} {n \choose k} f(k) \qquad \Leftrightarrow \qquad f(k) = \sum_j {k \choose j} h(j).$$

In the above problem, we are thus, modulo a sign $(-1)^n$, trying to solve for the (unique) $h(j)$ satisfying

$$k^{m+n} = \sum_j {k \choose j} h(j),$$

but notice that we can interpret $k^{m+n}$ combinatorially as the number of functions from an $(m+n)$-element set to a $k$-element set. Each such $f$ can be uniquely factored as a surjection followed by a subset inclusion; here ${k \choose j}$ counts the number of $j$-element subsets, and correspondingly $h(j)$ must be counting the number of surjections from an $(m+n)$-element set to a $j$-element set $[j] := \{1, 2, \ldots, j\}$. Such a surjection can be regarded as a partition of $[m+n]$ into $j$ nonempty classes together with a labeling of the classes by the elements $1, \ldots, j$, and there are $j!$ such labelings. The second Stirling number $S(m+n, j)$ is in fact combinatorially defined as the number of partitions on $[m+n]$ with $j$ classes, and so we have shown

$$h(j) = S(m+n, j) \cdot j!$$

or $h(n) = S(m+n, n) \cdot n!$, as indicated in the answer above.

$\endgroup$
1
$\begingroup$

Operationally, using the generalized Dobinski formula in the MO-Q on the o.g.f. for the Bell polynomials $\phi_m(x) = \sum_{k=0}^m S(m,k) x^k$,

$$ \phi_{n+m}(x) = (\phi.(x))^{n+m} = e^{-x} \sum_{j =0}^{\infty} j^{n+m} \frac{x^j}{j!} = \sum_{j=0}^{\infty} (-1)^j [\sum_{k=0}^j (-1)^k \binom{j}{k} k^{n+m}] \frac{x^j}{j!} \; . $$

Equivalently,

$$ \phi_{p}(\widehat{xD_x})= \sum_{k=0}^p S(p,k)x^kD_x^k = (xD_x)^p=\sum_{j=0}^\infty j^p \frac{x^jD^j_{x=0}}{j!}=\sum_{j=0}^\infty (-1)^j [\sum_{k=0}^j(-1)^k \binom{j}{k}k^p] \frac{x^jD_x^j}{j!} \; ,$$

where $D_x = \frac{d}{dx}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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