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

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

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 \( ... \) or \[ ... \] 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

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

Log in to reply

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

Log in to reply

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

Abhishek Bakshi - 5 years, 5 months ago

Log in to reply

Wow

Jianzhi Wang - 5 years, 5 months ago

Log in to reply

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

Victor Loh - 5 years, 5 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, 5 months ago

Log in to reply

Thank you.

Victor Loh - 5 years, 5 months ago

Log in to reply

The last identity is known as Vandermonde's Identity.

Siddhartha Srivastava - 5 years, 5 months ago

Log in to reply

Yay thanks :)

Victor Loh - 5 years, 5 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, 5 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...