1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Combinatorial Proof

  1. Jan 17, 2012 #1
    1. The problem statement, all variables and given/known data

    For some [itex]n, k \in \mathbb{N}[/itex], where [itex]n > k[/itex], prove

    [itex] \sum_{k = 1}^n k \cdot \binom{n}{k}^2 = n \cdot \binom{2n - 1}{n - 1}[/itex]

    by using the double counting proof technique.

    2. Relevant equations

    3. The attempt at a solution

    So we have to find a set of objects such that both the LHS and the RHS of the above equation count the number of objects in this set.

    It looks like the RHS of the above equation is easier to work with, so we should find out what the RHS counts, then show that the LHS counts these same objects.

    Suppose a committee consists of [itex]n[/itex] women and [itex]n - 1[/itex] men. Say we wish to construct a subcommittee of size [itex]n - 1[/itex] and choose one of the women to be the chief director of this subcommittee. We see that there are

    [itex]\binom{n + n - 1}{n - 1} \cdot \binom{n}{1} = n \cdot \binom{2n - 1}{n - 1}[/itex]

    ways of constructing such a committee and selecting a woman as the chief director. This gives us the RHS of the required equation, and this is where I get stuck. Ideas?

    Thank you!
  2. jcsd
  3. Jan 17, 2012 #2
    Got it.

    Instead of constructing a [itex]n - 1[/itex] size committee, construct a [itex]n[/itex] size committee and it is easy to see that the LHS equals the RHS.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook