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

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.

• This is probably a duplicate of something. See en.wikipedia.org/wiki/Vandermonde's_identity – Ragib Zaman Oct 16 '11 at 11:21
• @RagibZaman Please note that the running parameter is in the above of binomial coefficient. Different from Vandermonde's identity. – Fan Zhang Oct 16 '11 at 11:24
• The idea for proof is similar. It's a convolution, so figure which generating functions to multiply... – J. M. is a poor mathematician Oct 16 '11 at 11:28
• ... 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.$ – Gerben Oct 16 '11 at 12:07

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

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.

• Thank you for your answer, I have another problem that you maybe interested. May I know your email? – Fan Zhang Oct 16 '11 at 12:00
• @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. – Martin Sleziak Oct 16 '11 at 12:05

This approach is based on generating function.

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

• Please note that the running parameter is in the above of binomial coefficient which is different from Vandermonde. – Fan Zhang Oct 16 '11 at 14:32

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.

• THis is a variation, sure, but not the Vandermonde identity itself, which sums over the lower index and does not involve any "${}+1$". – Marc van Leeuwen Apr 22 '13 at 12:59
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.