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).

Any hints or directions please?

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

Edit: I think I got it:


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.


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}}$$

| cite | improve this answer | |
  • $\begingroup$ Why is $a^b=a(a−1)(a−2)⋯(a−b+1)$? $\endgroup$ – shinzou Apr 20 '15 at 18:35
  • $\begingroup$ It's not $a^b$ but $a^{\underline{b}}$, which is the falling factorial, and defined as $\frac {a!}{(a-b)!}$. $\endgroup$ – 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}.$$

| cite | improve this answer | |

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} &\bbox[10px,#ffd]{\sum_{k = 0}^{r}\pars{-1}^{k}{r \choose k}{n + r - k - 1 \choose r - k - 1}} = \sum_{k = 0}^{r}\pars{-1}^{k}{r \choose k}{-n - 1 \choose r - k - 1} \pars{-1}^{r - k - 1} \\[5mm] = &\ \pars{-1}^{r + 1}\sum_{k = 0}^{r}{r \choose k} \bracks{z^{r - k - 1}}\pars{1 + z}^{-n - 1} = \pars{-1}^{r + 1}\bracks{z^{r - 1}}\pars{1 + z}^{-n - 1} \sum_{k = 0}^{r}{r \choose k}z^{k} \\[5mm] = &\ \pars{-1}^{r + 1}\bracks{z^{r - 1}}\pars{1 + z}^{-n - 1 + r} = \pars{-1}^{r + 1}{-n - 1 + r \choose r - 1} \\[5mm] = &\ \pars{-1}^{r + 1}{n - 1 \choose r - 1}\pars{-1}^{r - 1} = \bbx{\large{n - 1 \choose r - 1}} \\ & \end{align}

| cite | improve this answer | |

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.