\(\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]

Log in to reply

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

Log in to reply

Wow

Log 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

Log in to reply

The last identity is known as Vandermonde's Identity.

Log in to reply

How do I prove it in a non-combinatorial way?

Log in to reply

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

Log in to reply

Thank you.

Log in to reply

Yay thanks :)

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

Log in to reply