Proving $\sum_{k = 0}^n k\binom nk^2 = n \binom{2n-1}{n-1}$ with combinatorial proof [duplicate]

Prove that $$\sum_{k = 0}^n k\binom nk^2 = n \binom{2n-1}{n-1}$$

I have to prove it in a combinatorically. No induction or algebra.

marked as duplicate by Potato, Dan Rust, Start wearing purple, rschwieb, Andrey RekaloAug 20 '13 at 19:13

Since you "have to prove it", I will assume this is some sort of homework, and give you a hint rather than a complete answer.

Can you argue combinatorially that:

• $\displaystyle k \binom n k = n \binom{n-1}{k-1}$; and
• $\displaystyle \sum_{k=0}^n \binom{n-1}{k-1}\binom n k = \binom{2n-1}{n-1}$?

Given these two ingredients, I'm confident you can conclude.

HINT: Imagine that you have a group of $n$ women and $n-1$ men. From this group you’re to choose a team of $n$ people and appoint one of them to be the team captain. It should be pretty clear that the righthand side gives the number of ways to do this, so you need only figure out why the lefthand side does so as well. You may find it useful to recall (or prove, if you’ve not seen it before) that

$$k\binom{n}k=n\binom{n-1}{k-1}\;,$$ so that

$$k\binom{n}k^2=n\binom{n-1}{k-1}\binom{n}{n-k}\;.$$