3
$\begingroup$

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

  • 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...2012-05-07

3 Answers 3

2

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

  • 0
    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 from2012-05-07
  • 0
    @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?2012-05-07
  • 0
    $(k+l) \times (k-l) = k^2 - l^2$2012-05-07
  • 0
    @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.2012-05-07
  • 0
    Thanks for the help. This cleared things up !2012-05-07
3

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$).

  • 0
    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.2012-05-07
  • 0
    @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.2012-05-07
  • 0
    Alright. Thanks.2012-05-07
2

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).