Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Question

Prove that if $k$ and $l$ are two positive integer with $k ≥ l$, then $\binom{2k}{2} =\binom{k−l}{2}+ \binom{k+l}{2}+ k^2 − l^2$ using a combinatorial argument.

I tried using Vandermonde's Identity and Pascal's Identity but that's leading me nowhere. Any lead is very welcome.

Thanks

share|improve this question
3  
If a set of size $2k$ is partitioned into two sets, one of size $k-l$ and one of size $k+l$, then the selection of two elements from the original set may be accomplished in a few different ways... –  Will Orrick May 7 '12 at 19:13

3 Answers 3

up vote 2 down vote accepted

You want a combinatorial argument...

Say you have $2k$ items and you want to select $2$ of them. Divide the $2k$ items into two groups, one with $k+\ell$ items and one with $k-\ell$ items.

To select two items out of the overall $2k$, you could select two from the group of $k+\ell$ items; or two from the group of $k-\ell$ items; or you could select one from the group of $k+\ell$ and one from the group of $k-\ell$ items. If you add all three possibilities, you should get $\binom{2k}{2}$.

How many ways to pick two from $k+\ell$? How many ways to pick two from $k-\ell$? How many ways to pick one from $k+\ell$ and one from $k-\ell$?

share|improve this answer
    
I don't see exactly where this is heading. I can agree on the fact of splitting the initial $2k$ items group into two smaller ones but I don't get were the $k^2$ and $l^2$ are coming from –  BrainOverfl0w May 7 '12 at 20:11
    
@FredericJacobs: One summand comes from selectin both items from the first group one summand from selecting both items from the other group. The last terms must come from selecting one from each. In how many ways can you select one item from $k+\ell$ possibilities? $k+\ell$ ways, of course; in how many ways can we select one item from $k-\ell$ possibilities? $k-\ell$ ways, of course. But now you want to select first an item from $k+\ell$ possibilities, and then an item from $k-\ell$ possibilities. So you should multiply to get the total number of ways of doing both. What is that product? –  Arturo Magidin May 7 '12 at 20:13
    
$(k+l) \times (k-l) = k^2 - l^2$ –  BrainOverfl0w May 7 '12 at 20:21
    
@FredericJacobs: So now you know where the $k^2$ and $\ell^2$ are coming from: they are coming from the case in which you pick one item from each of the two subsets. –  Arturo Magidin May 7 '12 at 20:22
    
Thanks for the help. This cleared things up ! –  BrainOverfl0w May 7 '12 at 20:23

Suppose you want to pick $2$ elements from a set of $2k$ elements. Color $k-l$ of the elements blue, and the remaining $k+l$ elements red. Then you can either pick $2$ blue elements (in ${k-l} \choose 2$ ways), or $2$ red elements (in ${k+l} \choose 2$ ways), or you can pick one blue element and one red element (in $(k-l)(k+l)=k^2-l^2$ ways).

share|improve this answer

Hint: The left-hand side is the number of ways to choose $2$ items out of $2k$. The right-hand side can be interpreted as the number of ways to choose $2$ items out of one subset, two items out of the remaining subset, and one item from each (using $(a+b)(a-b)=a^2-b^2$).

share|improve this answer
    
I see how you could use this as an algebraic proof but I don't think this can be used to prove it using a combinatorial argument. –  BrainOverfl0w May 7 '12 at 20:12
    
@FredericJacobs: He is giving you a combinatorial argument, not an algebraic one; don't be distrcted by the formula $(a+b)(a-b)=a^2-b^2$, that just covers one of the possibilities; joriki is using the same combinatorial argument as I did. –  Arturo Magidin May 7 '12 at 20:20
    
Alright. Thanks. –  BrainOverfl0w May 7 '12 at 20:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.