I need to prove that $$\sum_{r=0}^k\binom{k}{r}(-1)^r r^n=0$$ when $n<k$.

I know that the formula above can be easily transformed into the Stirling number of the Second kind formula, which is derived from combinatorics (number of ways to split $n$ objects into $k$ groups) meaning it must be $0$ when $n<k$. I'd like to see if one can prove this without using combinatorics.

I haven't tried much since I have no idea where to start, any suggestion would be welcome.

(The problem arised while doing some calculations regarding Bernoulli numbers)

  • $\begingroup$ "I'd like to see if one can prove this without using combinatorics." OH. =( $\endgroup$ – Pedro Tamaroff Sep 8 '14 at 2:01

Related technique: (I). Here is an approach. Recalling the identities

$$ \sum_{r=0}^k\binom{k}{r}x^r = (1+x)^k $$

$$ (xD)^n = \sum_{m=0}^{n} {n\brace m} x^mD^m $$

where $D=\frac{d}{dx}$ and $ {n\brace m} $ is the Stirling numbers of the second kind. Applying the operator $(xD)^n$ to both sides of the first identity gives

$$ (xD)^n\sum_{r=0}^k\binom{k}{r} x^r = \sum_{r=0}^k\binom{k}{r} r^n x^r = (xD)^n (1+x)^k .$$

I think you can finish the problem. Remember that you need to substitute $x=-1$ at the end. Note that if you substitute $x=-1$ in the first identity you will get zero.

  • $\begingroup$ Where do you use the fact that $n<k$ $\endgroup$ – Julio Cáceres Jun 26 '14 at 14:52
  • 1
    $\begingroup$ Nevermind, got it $\endgroup$ – Julio Cáceres Jun 26 '14 at 15:32

Observe that $$r^n = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp(rz) \; dz.$$ This gives for the sum that $$\sum_{r=0}^k {k\choose r} (-1)^r r^n = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \sum_{r=0}^k {k\choose r} (-1)^r \exp(rz) \; dz$$ This is $$\frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \left(1-\exp(z)\right)^k \; dz.$$ Note however that $$1-\exp(z) = -\frac{z^1}{1!} -\frac{z^2}{2!} -\frac{z^3}{3!}-\cdots$$ Therefore $(1-\exp(z))^k$ starts at $[z^k]$ and hence when $k\gt n$ the integrand is an entire function and the integral vanishes.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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