2
$\begingroup$

I got the following identity from commutative algebra.

I am curious to see elegant elementary methods.

$$ {{a+b+c-1}\choose c} = \sum_{i+j=c} {{a+i-1}\choose i}{{b+j-1}\choose j} $$

$\endgroup$
  • 3
    $\begingroup$ Consider $$\frac{1}{(1-z)^a} \frac{1}{(1-z)^b} = \frac{1}{(1-z)^{a+b}}.$$ $\endgroup$ – Marko Riedel Dec 27 '15 at 23:09
4
$\begingroup$

It is just a case of Vandermonde's identity.

The LHS is the coefficient of $x^c$ in $\frac{1}{(1-x)^{a+b}}$, by stars and bars.

On the other hand, $\frac{1}{(1-x)^{a+b}}=\frac{1}{(1-x)^{a}}\cdot\frac{1}{(1-x)^b}$, hence:

$$\begin{eqnarray*} \binom{a+b+c-1}{c}=[x^c]\frac{1}{(1-x)^{a+b}}&=&\sum_{d=0}^{c}[x^d]\frac{1}{(1-x)^a}\cdot [x^{c-d}]\frac{1}{(1-x)^b}\\ &=& \sum_{i+j=c}\binom{a+i-1}{i}\binom{b+j-1}{j}, \end{eqnarray*}$$ as wanted.

$\endgroup$
  • $\begingroup$ (+1). Did you see my comment? $\endgroup$ – Marko Riedel Dec 27 '15 at 23:13
  • $\begingroup$ Hi @MarkoRiedel: I saw your comment when I was writing my answer, we came almost at the same time :) $\endgroup$ – Jack D'Aurizio Dec 27 '15 at 23:14
  • 3
    $\begingroup$ It is just a case of Vandermonde's identity. - You sound just like a politician trying to calm the public and prevent mass hysteria in times of imminent danger... :-$)$ $\endgroup$ – Lucian Dec 28 '15 at 13:49
2
$\begingroup$

Using the identity $$ \sum_{j=0}^n\binom{n-j}{k}\binom{j}{m}=\binom{n+1}{k+m+1} $$ proven in this answer, we get $$ \begin{align} \sum_{i+j=c}\binom{a+i-1}{i}\binom{b+j-1}{j} &=\sum_{i+j=c}\binom{a+i-1}{a-1}\binom{b+j-1}{b-1}\\ &=\binom{a+b+c-1}{a+b-1}\\ &=\binom{a+b+c-1}{c}\\ \end{align} $$

$\endgroup$
1
$\begingroup$

For variety's sake here is a slightly different approach. Suppose we seek to evaluate

$$\sum_{k=0}^c {k+a-1\choose a-1} {b-1+c-k\choose b-1}.$$

Introduce $${b-1+c-k\choose b-1} = {b-1+c-k\choose c-k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{c-k+1}} (1+z)^{b-1+c-k} \; dz.$$

Observe that this is zero when $k\gt c$ so we may extend $k$ to infinity to get for the sum

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{c+1}} (1+z)^{b-1+c} \sum_{k\ge 0} {k+a-1\choose a-1} \frac{z^k}{(1+z)^k} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{c+1}} (1+z)^{b-1+c} \frac{1}{(1-z/(1+z))^a} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{c+1}} (1+z)^{a+b-1+c} \frac{1}{(1+z-z)^a} \; dz \\ = {a+b+c-1\choose c}.$$

$\endgroup$
  • $\begingroup$ (+1) I appreciate different approaches, and although this works on the coefficients of $(1+z)^{-k}$, residues is a nice method of computation. $\endgroup$ – robjohn Dec 28 '15 at 0:24
  • $\begingroup$ I often answer questions like this one using the Egorychev method which has the advantage that it includes very simple problem instances (see above) yet it can be extended to compute rather complicated binomial sums. A simple example might encourage the reader to try the method on more challenging ones involving convolutions of several binomial coefficients. $\endgroup$ – Marko Riedel Dec 28 '15 at 2:00

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.