# Prove with sets and combinatorial form $\sum_{k=0}^n k{n \choose k}^2=n{2n-1 \choose n-1}$

For the first part (The combinatorial form): Suppose you have a group consisting of n boys and n girls. A team of n has to be formed out of them, and a captian designated of the team, which has to be a girl. On one hand, one can fix the number k of girls and n−k of boys on the team first, then choose the team in one of ${n\choose k}{n \choose n−k}$ ways and a captain in one of k ways, so the left hand side counts the number of possible selections. On the other hand one could start out to choose one of the n girls as captain, and let her choose n−1 team mates among the remaining 2n−1 children; this is counted by the right hand side.

But I can´t find an example for the set form. Any tips for that?

• When you say "prove with sets" and "set form," what are you looking for exactly? – Mike Earnest Sep 25 '17 at 23:19

## 2 Answers

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

One has $$(x+1)^n = \sum_{k=0}^n {n \choose k}x^k$$ Then $$n(x+1)^{n-1} = \sum_{k=1}^n k{n \choose k}x^{k-1}$$

So $$n(x+1)^{2n-1} = \left(\sum_{k=0}^n {n \choose k}x^k\right)\left(\sum_{k=1}^n k{n \choose k}x^{k-1}\right)$$

The coefficient of $x^{n-1}$ in the LHS is $n{2n-1\choose n-1}$, and in the RHS is $\sum_{k=0}^n k{n\choose k}{n\choose n-k}$.

• In your second line, you meant to write $$n(x + 1)^{n - 1} = \sum_{k = 1}^{n} \color{red}{k}\binom{n}{k}x^{k - 1}$$ – N. F. Taussig Sep 26 '17 at 8:28
• My mistake. Thanks. – GAVD Sep 26 '17 at 8:29