Binomial coefficients

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

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

They satisfy(ni)+(ni1)=(n+1i) for i>0\text{They satisfy}{n \choose i}+{n \choose i-1}={n+1 \choose i} \text{ for } i > 0

and also(n0)+(n1)++(nn)=2n,\text{and also} {n \choose 0}+{n\choose 1}+\cdots+{n \choose n}=2^{n},

(n0)(n1)++(1)n(nn)=0,{n \choose 0}-{n\choose 1}+\cdots+(-1)^{n}{n \choose n}=0,

(n+mk)=i=0k(ni)(mki).{n+m \choose k}=\sum\limits_{i=0}^k {n \choose i} {m \choose k-i}.

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

(n+mk)=i=0k(ni)(mki)?{n+m \choose k}=\sum\limits_{i=0}^k {n \choose i} {m \choose k-i}?

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

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

Victor\text{Victor}

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

Note by Victor Loh
5 years, 2 months ago

No vote yet
1 vote

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

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Here's a combinatorial proof.

Question:

From a group of m+nm+n students consisting of nn boys and mm girls, how many ways are there to form a team of kk students?

Answer 1:

(n+mk){n+m}\choose{k}.

Answer 2:

If that team has ii boys, then it'll have kik-i girls. How many ways are there to choose ii boys from nn boys? (ni)n\choose i.

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

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

Since ii could be any number from 00 to kk, we add the number ways to form the team for different values of ii.

So, our final count is,

i=0k(ni)(mki)\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 - 5 years, 2 months ago

Log in to reply

Wow

Jianzhi Wang - 5 years, 2 months ago

Log in to reply

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

Abhishek Bakshi - 5 years, 2 months ago

Log in to reply

The last identity is known as Vandermonde's Identity.

Siddhartha Srivastava - 5 years, 2 months 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(1+x)^{ n } . again rewrite the binomial expansion of(x+1)m(x+1)^{ m } . Note that you should expand (x+1)m(x+1)^{ m } not (1+x)m(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(x+1)^{ m+n } Hence prooved

Anish Kelkar - 5 years, 2 months ago

Log in to reply

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

Finn Hulse - 5 years, 2 months ago

Log in to reply

Yay thanks :)

Victor Loh - 5 years, 2 months ago

Log in to reply

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

Victor Loh - 5 years, 2 months ago

Log in to reply

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

Abhishek Sinha - 5 years, 2 months ago

Log in to reply

Thank you.

Victor Loh - 5 years, 2 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...