12
$\begingroup$

How do I prove that

$\sum_{0 \le k \le t} {t-k \choose r}{k \choose s}={t+1 \choose r+s+1} \>?$

I saw this in a book discussing generating functions.

  • 0
    ... and remember that the coefficients of a product of polynomials are given by the following expression: $(\sum_k a_k X^k)(\sum_l b_l X^l) = \sum_n c_n X^n,$ where $c_n = \sum_{k + l = n} a_k b_l.$2011-10-16

6 Answers 6

0

Suppose we seek to verify that $\sum_{0\le k\le t} {t-k\choose r} {k\choose s} = {t+1\choose r+s+1}.$

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

This controls the range so we may extend $k$ to infinity, getting for the sum

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

This evaluates to ${t+1\choose t-r-s} = {t+1\choose r+s+1}$ by inspection.

8

Let $r$, $t$, $s$ be fixed.

$\binom{t+1}{r+s+1}$ = number of possibilities how can I choose $r+s+1$ elements from $\{1,2,\dots,t+1\}$

Let us order the chosen elements increasingly: $a_1 < a_2 < \dots < a_{r+s+1}$

What is the number of possibilities where $a_{s+1}=k+1$? We have to choose $s$ elements from $\{1,2,\dots,k\}$ and the remaining $r$ elements from $\{k+2,\dots,t+1\}$. We have $\binom ks \cdot \binom {t-k}r$ possibilities.

The last expression is non-zero only for $k\ge 0$ and $t-k\ge 0$, which gives us the range of summation.


Although you are probably not interested in a combinatorial proof, since you explicitly mentioned generating functions.

  • 3
    @FanZhang If you have another interesting problem I do not see the reason why not posting it here. (You have much better chance of getting the answer than by emailing it to me.) However my email is no big secret - you should be able to find it if you look at my profile.2011-10-16
5

I'm going to make more explicit the point I think Phira is making. The identity really is just Vandermonde's convolution plus the upper negation rule for binomial coefficients.

The upper negation rule for binomial coefficients is $\binom{n}{k} = (-1)^k \binom{k-n-1}{k},$ which holds when $k$ is an integer (see, for example, Concrete Mathematics, 2nd edition, p. 164). Applying this, we get $\sum_{0 \le k \le t} {t-k \choose r}{k \choose s} = \sum_{0 \le k \le t} {t-k \choose t-k-r}{k \choose k-s}= \sum_{0 \le k \le t} (-1)^{t-k-r}{-r-1 \choose t-r-k} (-1)^{k-s}{-s-1 \choose k-s}$ $ = (-1)^{t-r-s}\sum_{0 \le k \le t}{-r-1 \choose t-r-k}{-s-1 \choose -s+k}.$ Now, use Vandermonde's convolution (or, more generally, the Chu-Vandermonde identity), to get $ = (-1)^{t-r-s}{-r-s-2 \choose t-r-s},$ and then apply the upper negation rule again, which gives us what we want: $={t+1 \choose t-r-s} = {t+1 \choose r+s+1}.$

3

This approach is based on generating function.

By http://math.arizona.edu/~faris/combinatoricsweb/generate.pdf

We know that $\sum \limits_{n=0}^{\infty} {n \choose k} y^n= \frac{y^k}{(1-y)^{k+1}} $

$x \cdot \sum \limits_{l=0}^{\infty} {l \choose r} x^l \cdot \sum \limits_{k=0}^{\infty} {k \choose s} x^k = x \cdot \frac{x^r}{(1-x)^{r+1}} \cdot \frac{x^s}{(1-x)^{s+1}} =\frac{x^{r+s+1}}{(1-x)^{r+s+2}} = \sum \limits_{n=0} {n \choose r+s+1} x^n$

The coefficient of $x^{t+1}$ of the $x \cdot \sum \limits_{l=0}^{\infty} {l \choose r} x^l \cdot \sum \limits_{k=0}^{\infty} {k \choose s} x^k $ is $\sum \limits_{l+k=t} {l \choose r}{k \choose s}$

Let $n=t+1$, ${t+1 \choose r+s+1} = \sum \limits_{l+k=t} {l \choose r}{k \choose s} = \sum \limits_{0 \le k \le t} {t-k \choose r}{k \choose s}$

0

Look http://fatosmatematicos.blogspot.com/2011/06/algumas-demonstracoes-da-convolucao-de.html

  • 2
    Please note that the running parameter is in the above of binomial coefficient which is different from Vandermonde.2011-10-16
0

Note that this summation is Vandermonde's identity.

Calculate in both sums the ratio of consecutive summands and compare them. You will see that after a suitable change of variables they are the same.

Therefore, the two sums only differ by a global factor in each term and the result.

If you want to know more about this, read about hypergeometric functions.

  • 0
    THis is a variation, sure, but not the Vandermonde identity itself, which sums over the _lower_ index and does not involve any "${}+1$".2013-04-22