# How to begin Combinatorial Proof

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

## 1 Answer

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? –  alexthebake 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