Use the PIE to prove an identity

Question

Use the PIE to prove,

$n!{{n-1}\choose {k-1}} = \sum_{i=1}^k (-1)^{k-i} {k \choose i} \bar i^{n}, \ 1 \le k \le n$

Where, $\bar i^{n}= i(i+1)...(i+n-1)$

Edit

Actually,I can solve it now. And it's a cool question. So leaving it for my fellow friends out there.

Answer 1

You’re right: it is a cute question. I’ll use the notation $i^{\overline n}$ for the rising factorial, however. First we note that

$$\begin{align*} \sum_{i=1}^k(-1)^{k-i}\binom{k}ii^{\overline n}&=\sum_{i=1}^k(-1)^{k-i}\binom{k}i\frac{(n+i-1)!}{(i-1)!}\\\\ &=n!\sum_{i=1}^k(-1)^{k-i}\binom{k}i\binom{n+i-1}{i-1}\;, \end{align*}$$

so the identity reduces to

$$\binom{n-1}{k-1}=\sum_{i=1}^k(-1)^{k-i}\binom{k}i\binom{n+i-1}{i-1}\;.\tag{1}$$

The lefthand side of $(1)$ is the number of ways of distributing $n$ indistinguishable objects amongst $k$ distinguishable boxes so that no box is empty. The binomial coefficient $\binom{n+i-1}{i-1}$ is the number of ways of distributing $n$ indistinguishable objects amongst $i$ distinguishable boxes, where the boxes are allowed to be empty. Thus,

$$\binom{k}i\binom{n+i-1}{i-1}$$

is the number of ways of distributing $n$ indistinguishable objects amongst $k$ distinguishable boxes so that at least $k-i$ boxes are empty, and $(1)$ follows immediately by the inclusion-exclusion principle.

Answer 2

By way of enrichment I present an algebraic proof. I upvoted @Brian M. Scotts's answer.

Suppose we are trying to prove $${n-1\choose k-1} = \frac{1}{n!} \sum_{q=0}^k (-1)^{k-q} {k\choose q} q^{\overline{n}}$$ where $1\le k\le n.$

This is $${n-1\choose k-1} = \sum_{q=0}^k (-1)^{k-q} {k\choose q} {q+n-1\choose n}.$$

Introduce the integral representation $${q+n-1\choose n} =\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{q+n-1}}{z^{n+1}} \; dz.$$

This gives for the sum the integral $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n-1}}{z^{n+1}} \sum_{q=0}^k (-1)^{k-q} {k\choose q} (1+z)^q \; dz$$ which simplifies to $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n-1}}{z^{n+1}} (1+z-1)^k \; dz$$ or $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n-1}}{z^{n-k+1}} \; dz.$$

This can be evaluated by inspection to give $${n-1\choose n-k} = {n-1\choose k-1}.$$

Of course when $k\ge n+1$ the integrand turns into an entire function giving the value zero.