$\sum_{k=0}^{a}\binom{a}{k}\binom{b}{k}=\binom{a+b}{a}=\binom{a+b}{b}$ when a\leq b.
For equality, $\sum_{k=0}^{a}\binom{a}{k}^{2}=\binom{2a}{a}$
How do u prove it?
Help 2 prove (Combi.)
Re: Help 2 prove (Combi.)
You can use a combinatorial argument as follows: there are $a$ boys and $b$ girls in a class. We are trying to choose a team of $a$ students from among the $a+b$ students. In how many ways can this be done?
The answer is clearly $\binom{a+b}{a}=\binom{a+b}{b}$.
We can do the same by choosing $k$ girls first and then $a-k$ boys. This can be done in $\binom{a}{a-k}\binom{b}{k}=\binom ak\binom bk$ ways. Summing this from $k=0$ to $k=a$ gives us the total number of ways.
Now equate the two answers.
The general result is known as Vandermonde's identity, which you can prove using a similar argument.
The answer is clearly $\binom{a+b}{a}=\binom{a+b}{b}$.
We can do the same by choosing $k$ girls first and then $a-k$ boys. This can be done in $\binom{a}{a-k}\binom{b}{k}=\binom ak\binom bk$ ways. Summing this from $k=0$ to $k=a$ gives us the total number of ways.
Now equate the two answers.
The general result is known as Vandermonde's identity, which you can prove using a similar argument.
"Everything should be made as simple as possible, but not simpler." - Albert Einstein
Re: Help 2 prove (Combi.)
Wow, that was easy... & intelligent,too! However, I came up with a twisted critical proof today . Plz suggest me some effective books on Combinatorics(other than the 3 in the last camp) that cover some advanced topics.
Re: Help 2 prove (Combi.)
I can think of 'A Path to Combinatorics for Undergraduates' by Titu Andreescu and Zuming Feng (not sure whether it was given to you in the camp). You can also read the chapter on combinatorics in 'Art and Craft of Problem Solving' by Paul Zeitz.
"Everything should be made as simple as possible, but not simpler." - Albert Einstein