Waste less time on Facebook — follow Brilliant.
×

Binomial coefficients

\(\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 :)}\)

Note by Victor Loh
3 years ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Here'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

@Mursalin Habib yeah, that is the actual proof...by counting in 2 ways. Abhishek Bakshi · 3 years ago

Log in to reply

@Mursalin Habib Wow Jianzhi Wang · 3 years ago

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

@Victor Loh Consider the coeff of \(x^k\) of both sides in \((1+x)^n (1+x)^m=(1+x)^{n+m}\) Abhishek Sinha · 3 years ago

Log in to reply

@Abhishek Sinha Thank you. Victor Loh · 3 years ago

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

×

Problem Loading...

Note Loading...

Set Loading...