# Proving combinatorially $\sum_{k=0}^n k \binom n k ^2=n\binom{2n-1}{n-1}$

Prove with a combinatorial proof (story): $\displaystyle\sum_{k=0}^n k \binom n k ^2=n\binom{2n-1}{n-1}$

My attempt:

Let's make it easier to work with (it's very easy to show that identity): $\displaystyle\sum_{k=0}^n \frac kn \binom n k ^2=\binom{2n-1}{n-1}\Rightarrow \sum_{k=0}^n \binom {n-1}{k-1} \binom n k =\binom{2n-1}{n-1}$

RHS: we want to form a group of size $n-1$ from $2n-1$ people.

LHS: The group has $n$ men and $n-1$ women. We'll choose the men and women such that there will always be $1$ men more than women:

No men - no way to form such group.

$1$ person - $n=\binom {n-1} 0 \binom {n} 1$.

$3$ people - $\binom{n-1} 1\binom n 2$

...

$n$ people - $\binom{n-1} {n-1}\binom n n$

And if we sum up all the different cases we get: $\displaystyle\sum_{k=0}^n \binom {n-1}{k-1} \binom n k$

I'm not convinced with my story for the LHS, picking the groups such that there will always be $1$ men more seems too arbitrary. Also I'm pretty sure the first and last cases are wrong. Any tips on how fix it?

Note: no integrals nor use of other identities without proving them nor generating functions.

## 1 Answer

Left-hand side: Pick $k$ women to include, and $k$ men to exclude, to form a team of $n$ people. Choose one of the $k$ women to lead.
Right-hand side: Pick one of the $n$ women to lead. Pick $n-1$ of the other $2n-1$ people to form the team.

• Why would it be the same if we exclude men? – shinzou Mar 20 '15 at 16:03
• There are $n$ men and $n$ women. If the team has $n$ people and $k$ women, then $k$ men miss out. – Empy2 Mar 20 '15 at 16:05
• Right, it's clearer to see it with: $\binom n k = \binom n {n-k}$. One more thing, could the given expression be wrong for $k=0$? – shinzou Mar 20 '15 at 16:19
• I think $n-1\choose-1$ is defined to equal zero, which equals the corresponding term on the left-hand side. – Empy2 Mar 20 '15 at 16:25
• I'm getting the same problem when trying to explicitly show every case of the sum: a team of 1 member is supposed to be to choose 1 women ($n$) but on the LHS we get $n^2$. – shinzou Mar 20 '15 at 16:40