×

# 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, 5 months ago

Sort by:

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?

${n+m}\choose{k}$.

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]

- 3 years, 5 months ago

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

- 3 years, 4 months ago

Wow

- 3 years, 5 months ago

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

- 3 years, 4 months ago

The last identity is known as Vandermonde's Identity.

- 3 years, 5 months ago

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

- 3 years, 5 months ago

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

- 3 years, 5 months ago

Thank you.

- 3 years, 5 months ago

Yay thanks :)

- 3 years, 5 months ago

That's funny that you used $$\LaTeX$$ on the whole thing. Yes, I will surely work on this cool identity. :D

- 3 years, 5 months ago