Combinatorial proofs of the equation $\sum_{k=0}^{n} k{n \choose k}^2 = n {2n-1 \choose n-1}$

Question

$$ \sum_{k=0}^{n} k{n \choose k}^2 = n {2n-1 \choose n-1}$$ How can we prove this? Basically, my method to choose a list of length $n$ from a list of length $2n$. We specify a specific element, then I got $${2n-1 \choose n-1}$$ as we select n elements, it becomes:$$n {2n-1 \choose n-1}$$ How can we use this to prove it?

Another method is to make a middle pivot in $2n$ list, choose $i-1$ from the front $n$ elements, and choose $n-(i-1)$ elements from back list.(*2 as we can do this to back last) we get $$2{n-1 \choose i-1}{n \choose n-(i-1)}$$ How can we use this to prove it?

Answer 1

Suppose we have $n$ men and $n$ women. The RHS of your identity counts the number of $n$ person committees that can be formed with a specific woman in charge.

For the LHS, once we select $k$ women to be on the committee with one of them leading, there are $k\binom{n}{k}$ ways to do this. The remaining positions are filled by $\binom{n}{n-k}=\binom{n}{k}$ men. Thus there are $$ \sum_{k=0}^nk\binom{n}{k}^2 $$ ways to do this.

Answer 2

Here is an alternative to the nice answer above; I think it is useful to know the generating function style of proof for when the combinatorial intuition fails.

The right hand side of your above equation is (using binomial expansion of powers of $(1+X)$) the coefficient of $x^n$ in $n(1+X)^{2n-1}$. Alternatively, you may write $$n(1+X)^{2n-1}=n(1+X)^{n-1}(1+X)^n$$ Using the fact that $n(1+X)^{n-1}$ is the derivative of $(1+x)^n$, we get $$n(1+X)^{n-1}=\sum k\binom{n}{k}X^{k-1}$$ Multiplying the right hand side above by $(1+X)^n=\sum\binom{n}{k}X^{k}$ and examining coefficients gives you the desired identity.