Help 2 prove (Combi.)

For students of class 9-10 (age 14-16)
Rabeeb
Posts:25
Joined:Tue Dec 14, 2010 7:52 pm
Location:Mymensingh, Bangladesh
Contact:
Help 2 prove (Combi.)

Unread post by Rabeeb » Thu Sep 19, 2013 3:36 pm

$\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?

User avatar
nayel
Posts:268
Joined:Tue Dec 07, 2010 7:38 pm
Location:Dhaka, Bangladesh or Cambridge, UK

Re: Help 2 prove (Combi.)

Unread post by nayel » Thu Sep 19, 2013 10:27 pm

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.
"Everything should be made as simple as possible, but not simpler." - Albert Einstein

Rabeeb
Posts:25
Joined:Tue Dec 14, 2010 7:52 pm
Location:Mymensingh, Bangladesh
Contact:

Re: Help 2 prove (Combi.)

Unread post by Rabeeb » Fri Sep 20, 2013 6:57 pm

Wow, that was easy... & intelligent,too! However, I came up with a twisted critical proof today :lol: . Plz suggest me some effective books on Combinatorics(other than the 3 in the last camp) that cover some advanced topics.

User avatar
nayel
Posts:268
Joined:Tue Dec 07, 2010 7:38 pm
Location:Dhaka, Bangladesh or Cambridge, UK

Re: Help 2 prove (Combi.)

Unread post by nayel » Sat Sep 21, 2013 8:02 pm

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

Post Reply