Prove $\binom{N+K-1}{K}=\sum_{i=1}^{N-1} (-1)^{i+1}\binom{N}{i}\binom{N-i+K-1}{K}$ using polynomial

Question

I find the identity, $$\binom{N+K-1}{K}=\sum_{i=1}^{N-1} (-1)^{i+1}\binom{N}{i}\binom{N-i+K-1}{K}$$

by counting the number of ways to distribute $K$ candies to $N$ people ($N>K)$.

For right-hand eq., I count the number of ways to distribute candies when there is at least $i$ people who cannot get candies.

Can we prove this identity using polynomials?

For left-hand eq., it corresponds to the coefficient of $x^K$ of $\frac{1}{(1-x)^N}$. Can we get the right-hand eq. by manipulating this polynomial?

Answer 1

We can re-write the identity as

$$\sum_{q=0}^{N-1} (-1)^{q+1} {N\choose q} {N-q+K-1\choose K} = 0.$$

Equivalently (divide by $-1$),

$$\sum_{q=0}^{N-1} (-1)^q {N\choose q} {N-q+K-1\choose N-1-q} \\ = \sum_{q=0}^{N-1} (-1)^q {N\choose q} [z^{N-1-q}] (1+z)^{N-q+K-1} \\ = [z^{N-1}] (1+z)^{N+K-1} \sum_{q=0}^{N-1} (-1)^q {N\choose q} z^q (1+z)^{-q}.$$

Now we may add in the term for $q=N$ because it does not contribute to the coefficient extractor:

$$[z^{N-1}] (1+z)^{N+K-1} \sum_{q=0}^{N} (-1)^q {N\choose q} z^q (1+z)^{-q} \\ = [z^{N-1}] (1+z)^{N+K-1} \left(1-\frac{z}{1+z}\right)^N \\ = [z^{N-1}] (1+z)^{K-1}.$$

This is zero by inspection when $N\gt K$ as claimed. We obtain ${K-1\choose N-1}$ when $N\le K.$

Remark. If an inverse binomial is insisted upon we may start from

$$\sum_{q=0}^{N-1} (-1)^q {N\choose q} {N-q+K-1\choose K} \\ = \sum_{q=0}^{N-1} (-1)^q {N\choose q} [z^{N-1-q}] \frac{1}{(1-z)^{K+1}} \\ = [z^{N-1}] \frac{1}{(1-z)^{K+1}} \sum_{q=0}^{N-1} (-1)^q {N\choose q} z^q.$$

Same action of the coefficient extractor as before:

$$[z^{N-1}] \frac{1}{(1-z)^{K+1}} \sum_{q=0}^{N} (-1)^q {N\choose q} z^q = [z^{N-1}] \frac{1}{(1-z)^{K+1}} (1-z)^N \\ = [z^{N-1}] \frac{1}{(1-z)^{K-N+1}}.$$

Now when $N\gt K$ this becomes $[z^{N-1}] (1-z)^{N-K-1}$ which is zero by inspection. With $N\le K$ we find ${N-1+K-N\choose K-N} = {K-1\choose K-N} = {K-1\choose N-1}$ in agreement with the previous result. We suppose in both versions that $N,K\ge 1.$