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

This question already has an answer here:

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

## 2 Answers

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}\;.$$