Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The question states to give a combinatorial proof for:

$$\sum_{k=1}^{n}k{n \choose k}^2 = n{{2n-1}\choose{n-1}}$$

Honestly, I have no idea how to begin. I want to do a two-way counting proof, looking at the LHS and the RHS correct? Any help would be greatly appreciated.

share|cite|improve this question
Did you try induction? – Nikita Evseev Nov 5 '12 at 3:04
@nikita2: "Combinatorial proof" means no induction. – wj32 Nov 5 '12 at 3:08
up vote 8 down vote accepted

We have a group of $2n$ people, $n$ female and $n$ male. We want to select a committee of $n$ people, including a female Chair.

We can select the Chair first. There are $n$ ways to do this. For each of these ways, there are $\binom{2n-1}{n-1}$ ways to choose the rest of the committee. Thus there are $n\binom{2n-1}{n-1}$ ways to choose a committee with female Chair.

We now count the number of committees with female Chair in a different way. The committee will have a total of $k$ females, where $k$ ranges from $1$ to $n$, and $n-k$ males.

We can select $k$ females and $n-k$ males in $\binom{n}{k}\binom{n}{n-k}$ ways. For each of these ways, the Chair can be chosen from the $k$ females in $k$ ways. Thus there are $k\binom{n}{k}\binom{n}{n-k}$ ways to make a committee with $k$ females, including a female Chair, and $n-k$ males.

Finally, note that $\binom{n}{n-k}=\binom{n}{k}$, and sum over all $k$ from $1$ to $n$. The number of committees with female Chair is $\sum_{k=1}^n k\binom{n}{k}^2$.

share|cite|improve this answer
Can you briefly describe how you thought this story up? I'm simply curious. – Benjamin Dickman Nov 5 '12 at 3:12
Why is it $n-k$ males instead of $2n - k$ males? – atb Nov 5 '12 at 3:15
@alexthebake: You are trying to select $n$ people in total, so since there already $k$ females, there must be $n-k$ males. – wj32 Nov 5 '12 at 3:16
@alexthebake: Because we are making a committee of $n$ people. If we have $k$ females, we must have $n-k$ males. – André Nicolas Nov 5 '12 at 3:17

Your Answer


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.