# How to begin combinatorial proof of $\sum_{k=1}^n k \binom nk^2 = n \binom{2n-1}{n-1}$

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.

• 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
• – Martin Sleziak Jun 10 '18 at 5:15

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

• 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