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

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

$</code> ... <code>$</code>...<code>."> Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in $</span> ... <span>$ or $</span> ... <span>$ to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

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

Wow

Log in to reply

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

Log in to reply

The last identity is known as Vandermonde's Identity.

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

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

Yay thanks :)

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