Is there a nicer closed form expression for the following expression? $$\sum_{j=0}^k{n \choose k-j}{m \choose j}$$
$\begingroup$
$\endgroup$
5
asked May 3, 2013 at 9:55
-
1$\begingroup$ Vandermonde's Identity $\endgroup$– EuYuCommented May 3, 2013 at 10:00
-
$\begingroup$ If you search a little, you will find many proofs of this identity on this site. (Or some equivalent reformulations. It is much easier now that you know the name of this identity.) For example this one: Equality Exercise of summations with binomial coefficients. I am voting to close as a duplicate. $\endgroup$– Martin SleziakCommented May 3, 2013 at 12:11
-
$\begingroup$ @MartinSleziak: It is a tribute to the searching facility of this site that you needed Google to help out. Notably this search does not turn up that example, though it does come up with loads of things that aren't quite, or not as obviously, Vandermonde. $\endgroup$– Marc van LeeuwenCommented May 3, 2013 at 12:24
-
$\begingroup$ @MartinSleziak Apologies for the duplicate, but please note that it is difficult to search for this type of thing. The search engine is not particularly receptive to formulas. $\endgroup$– Samuel HandwichCommented May 3, 2013 at 17:50
-
$\begingroup$ @SamuelHandwich There is not need to apologize. It is perfectly ok to ask question, if you cannot find an older question, which is similar (or perhaps the same). On of the reason we try to close such questions as duplicates is to have answers in one place and not in several identical questions. But, as you can easily notice, it works far from perfect. (In some cases it is almost impossible to find duplicates, considering vast number of questions which have been asked here so far.) $\endgroup$– Martin SleziakCommented May 3, 2013 at 17:55
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
Yes, it is known as Vandermonde's identity: $$\sum_{j=0}^{k}\binom{n}{k-j}\binom{m}{j}=\binom{n+m}{k}$$
The right side is the number of ways of picking $k$ elements from $m+n$ elements, while the left side is the number of ways of doing the same thing: first pick all $k$ from the $n$ elements and nothing from $m$, then $k-1$ from $n$ and $1$ from $m$, and so on till you pick none from the $n$ elements and all $k$ from the $m$ elements.
-
$\begingroup$ Thanks. I hadn't heard of that. $\endgroup$ Commented May 3, 2013 at 17:49
$\begingroup$
$\endgroup$
This is Vandermonde's identity: $$ \sum_{j=0}^k\binom{n}{k-j}\binom{m}{j}=\binom{n+m}{k} $$ It computes the coefficient of $x^k$ in $$ (1+x)^n(1+x)^m=(1+x)^{n+m} $$
