\(\text{Binomial coefficients} { n\choose k}, n,k \in \mathbb{N}_0, k \leq n, \text{are defined as}\)

\[{n \choose i}=\frac{n!}{i!(n-i)!}\].

\[\text{They satisfy}{n \choose i}+{n \choose i-1}={n+1 \choose i} \text{ for } i > 0\]

\[\text{and also} {n \choose 0}+{n\choose 1}+\cdots+{n \choose n}=2^{n},\]

\[{n \choose 0}-{n\choose 1}+\cdots+(-1)^{n}{n \choose n}=0,\]

\[{n+m \choose k}=\sum\limits_{i=0}^k {n \choose i} {m \choose k-i}.\]

\(\text{How do I prove that}\)

\[{n+m \choose k}=\sum\limits_{i=0}^k {n \choose i} {m \choose k-i}?\]

\(\text{(Edit: This is also known as the Vandermonde's Identity.)}\)

\(\text{Help would be greatly appreciated. (I came across this in a book)}\)

\(\text{Victor}\)

\(\text{By the way, I used LaTeX to type the whole note :)}\)

## Comments

Sort by:

TopNewestHere's a combinatorial proof.

Question:From a group of \(m+n\) students consisting of \(n\) boys and \(m\) girls, how many ways are there to form a team of \(k\) students?

Answer 1:\[{n+m}\choose{k}\].

Answer 2:If that team has \(i\) boys, then it'll have \(k-i\) girls. How many ways are there to choose \(i\) boys from \(n\) boys? \(n\choose i\).

How many ways are there to choose \(k-i\) girls from \(m\) girls? \(m\choose{k-i}\).

So for a fixed \(i\), there are \({n\choose i}{m\choose {k-i}}\) ways to form a team of \(k\) students.

Since \(i\) could be any number from \(0\) to \(k\), we add the number ways to form the team for different values of \(i\).

So, our final count is,

\[\displaystyle \sum_{i=0}^k {n\choose i}{m\choose{k-i}}\]

Since answers 1 and 2 are counting the same thing, they must be equal.

[proved] – Mursalin Habib · 3 years ago

Log in to reply

– Abhishek Bakshi · 3 years ago

yeah, that is the actual proof...by counting in 2 ways.Log in to reply

– Jianzhi Wang · 3 years ago

WowLog in to reply

Deriving Vandermonde's identity is very simple . ( I am going to tell just the procedure ) First what you need to do is just right binomial expansion of \((1+x)^{ n }\) . again rewrite the binomial expansion of\((x+1)^{ m } \) . Note that you should expand \((x+1)^{ m } \) not \((1+x)^{ m } \). now multiplying these two expansions . we get the above summation which is equal to the one of the binomial coefficient in the expansion of \((x+1)^{ m+n } \) Hence prooved – Anish Kelkar · 3 years ago

Log in to reply

The last identity is known as Vandermonde's Identity. – Siddhartha Srivastava · 3 years ago

Log in to reply

How do I prove it in a non-combinatorial way? – Victor Loh · 3 years ago

Log in to reply

– Abhishek Sinha · 3 years ago

Consider the coeff of \(x^k\) of both sides in \((1+x)^n (1+x)^m=(1+x)^{n+m}\)Log in to reply

– Victor Loh · 3 years ago

Thank you.Log in to reply

Yay thanks :) – Victor Loh · 3 years ago

Log in to reply

That's funny that you used \(\LaTeX\) on the whole thing. Yes, I will surely work on this cool identity. :D – Finn Hulse · 3 years ago

Log in to reply