Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|cite|improve this question
This is probably a duplicate of something. See'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. 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

6 Answers 6

up vote 4 down vote accepted

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

share|cite|improve this answer

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.

share|cite|improve this answer
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}$

share|cite|improve this answer


share|cite|improve this answer
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.

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

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.