# Proving $\binom {n-1}{r-1}=\sum_{k=0}^r(-1)^k\binom r k \binom{n+r-k-1}{r-k-1}$

Prove the identity: $\displaystyle\binom {n-1}{r-1}=\sum_{k=0}^r(-1)^k\binom r k \binom{n+r-k-1}{r-k-1}$

It looks a bit similar to the "no gets their own hat back" problem or inclusion exclusion or non distinct balls in bins.

Trying to find a combinatorial solution seems like impossible because of the alternating sum (how can we explain inclusion exclusion?).

Trying to expand the RHS doesn't help nor using any of the simple identities I know of (like Pascal's).

Note: no integrals, no generating functions nor use of other identities without proving them.

Edit: I think I got it:

LHS:

n non distinct balls to r bins such that every bin has at least one ball, spread 1 ball to each bin, we're left with n-r balls to r bins.

RHS:

General case: $\binom {n+r-1}{r-1}$

complement: at least one bin is empty; 1 bin is empty, choose that bin $\binom r 1$ and spread the balls: $\binom{n+r-1-1}{r-1-1}$, do this up to r empty bins.

Since we have many over counting, we'll apply the inclusion exclusion principle and we got what we desired.

\begin{align} \sum_{k=0}^r(-1)^k\binom rk\binom{n+r-k-1}{r-k-1} &=\sum_{k=0}^r(-1)^k\binom rk\binom{-n-1}{r-k-1}(-1)^{r-k-1}&&(1)\\ &=(-1)^{r-1}\sum_{k=0}^r\binom rk\binom{-n-1}{r-1-k}\\ &=(_1)^{r-1}\binom{r-n-1}{r-1}&&(2)\\ &=(-1)^{r-1}\binom{n-1}{r-1}(-1)^{r-1}&&(3)\\ &=\binom{n-1}{r-1}\qquad\blacksquare \end{align}

(1): using Upper Negation
(2): using Vandermonde Identity
(3): using Upper Negation
__

$\color{gray}{\text{Proof of Upper Negation}}$ \color{gray}{\begin{align}\\ \binom ab&=\frac{a^{\underline{b}}}{b!} =\frac{a(a-1)(a-2)\cdots(a-b+1)}{b!}\\ &=(-1)^b \frac{[-a][-(a-1)][-(a-2)]\cdots[-(a-b+1)]}{b!}\\ &=(-1)^b \frac{(b-1-a)\cdots(2-a)(1-a)(-a)}{b!}\\ &=(-1)^b \binom{b-a-1}b\end{align}}

$\color{gray}{\text{Proof of Vandermonde Identity}}$ \color{gray}{\begin{align}\\ \sum_{i=0}^a\binom ai x^i\sum_{j=0}^b\binom bjx^j &=(1+x)^a(1+x)^b=(1+x)^{a+b}\\ [x^n]: \sum_{i+j=n}\binom ai\binom bj &=\underbrace{\sum_{i=0}^n \binom ai\binom b{n-i}=\binom{a+b}n}_{\text{Vandermonde Identity}} \end{align}}

• Why is $a^b=a(a−1)(a−2)⋯(a−b+1)$? – shinzou Apr 20 '15 at 18:35
• It's not $a^b$ but $a^{\underline{b}}$, which is the falling factorial, and defined as $\frac {a!}{(a-b)!}$. – Hypergeometricx Apr 20 '15 at 20:35

We seek to evaluate

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

Note that the second binomial coefficient is zero when $$k=r$$ because $$(n-1)^\underline{n} = 0.$$ Continuing we find

$$[z^n] (1+z)^{n+r-1} \sum_{k=0}^r (-1)^k {r\choose k} (1+z)^{-k} \\ = [z^n] (1+z)^{n+r-1} \left(1-\frac{1}{1+z}\right)^r = [z^n] (1+z)^{n+r-1} \frac{z^r}{(1+z)^r} \\ = [z^{n-r}] (1+z)^{n-1} = {n-1\choose n-r} = {n-1\choose r-1}.$$
