\(\text{Binomial coefficients} { n\choose k}, n,k \in \mathbb{N}_0, k \leq n, \text{are defined as}\)
(in)=i!(n−i)!n!.
They satisfy(in)+(i−1n)=(in+1) for i>0
and also(0n)+(1n)+⋯+(nn)=2n,
(0n)−(1n)+⋯+(−1)n(nn)=0,
(kn+m)=i=0∑k(in)(k−im).
How do I prove that
(kn+m)=i=0∑k(in)(k−im)?
(Edit: This is also known as the Vandermonde’s Identity.)
Help would be greatly appreciated. (I came across this in a book)
Victor
By the way, I used LaTeX to type the whole note :)
#BinomialCoefficients
#Help
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:
*italics*or_italics_**bold**or__bold__paragraph 1
paragraph 2
[example link](https://brilliant.org)> This is a quote# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"\(...\)or\[...\]to ensure proper formatting.2 \times 32^{34}a_{i-1}\frac{2}{3}\sqrt{2}\sum_{i=1}^3\sin \theta\boxed{123}Comments
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:
(kn+m).
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? (in).
How many ways are there to choose k−i girls from m girls? (k−im).
So for a fixed i, there are (in)(k−im) 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,
i=0∑k(in)(k−im)
Since answers 1 and 2 are counting the same thing, they must be equal.
[proved]
Log in to reply
Wow
yeah, that is the actual proof...by counting in 2 ways.
The last identity is known as Vandermonde's Identity.
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
That's funny that you used LATEX on the whole thing. Yes, I will surely work on this cool identity. :D
Yay thanks :)
How do I prove it in a non-combinatorial way?
Log in to reply
Consider the coeff of xk of both sides in (1+x)n(1+x)m=(1+x)n+m
Log in to reply
Thank you.