# Combination proof $\sum_{k=1}^nk\binom{n}{k}^2=n\binom{2n-1}{n-1}$

How can I show that k and n being integers

$\sum_{k=1}^nk\dbinom{n}{k}^2=n\dbinom{2n-1}{n-1}$

the following is true using a combination proof.

I am not sure how to do this. on the right hand side you have the set of n object and you are and out of the set (2n-1) object you chose n-1 and multiply by the set n.

On the right hand you chose a out n of object one item a k and square it and then multiply by this k object. For as many k item you have.

But how is it shown they equal?

Suppose there are $2n$ people, divided in two groups of $n$. We want to choose the same number of people $k$ ($1\leq k\leq n$) from both groups to play against each other in a match. For the first team, from the ones who play, we choose a leader. If we sum over all possibilities for $k$, we get the left hand side: $$\sum_{k=1}^nk\binom{n}{k}^2$$ We can also choose first pick a leader from the first $n$ people in $n$ ways. Then, we pick $n-1$ from the remaining $2n-1$ people. From the first half, we pick those people who will play and from the second half, we pick those people who won't play. Suppose we pick $k-1$ people from the first $n-1$ people. Then, $k$ people will play for the first team and $n-(n-1-(k-1))=k$ people will play for the second team. Thus, we count the same number of events as before. This yields the equality: $$\sum_{k=1}^nk\binom{n}{k}^2=n\dbinom{2n-1}{n-1}$$
• @FernandoMartinez, the $2n-1$ people are just the $2n$ people, except the leader, who is already chosen at that point. – Ragnar Feb 21 '14 at 23:32
$\sum_{k=1}^nk\dbinom{n}{k}^2=\sum_{k=1}^nk\dbinom{n}{k}\dbinom{n}{n-k}$ is the number of ways of ways of choosing a set of $n$ balls from two collections A and B of $n$ of identical balls, and declaring a ball taken from A as a 'good' ball.Where the $k$-th term in the summation in LHS corresponds to the case: $k$ balls picked from A and $n-k$ picked from B, and choosing one of $k$ balls taken from A as the good ball.
The same thing can be done by first choosing a good ball from A in $n$ ways and choosing remaining $n-1$ balls from total $2n-1$ balls left in collections A and B, after removal.Which can be done in $n\dbinom{2n-1}{n-1}$ ways.