Is this expression right? If yes how can I prove it combinatorially?

Question

Is it true that $\sum_kk\binom{n}{k}^2=n\binom{2n-1}{n-1}$? (I proved it using generating functions). Could you help me to prove it combinatorially? please

Answer 1

To obtain this combinatorially write left hand side as $\sum_k k {n \choose k} {n \choose n-k}$. This sum can be interpreted as the number of ways to choose $n$ children from a group of $n$ boys and $n$ girls ($2n$ children) and then choosing "leader" from, e.g., chosen boys.

On the other way it can be done as follows: choose a "leader" from boys group and then choose $n-1$ children from whole group of $2n-1$. That is $n {2n-1 \choose n-1}$.

Answer 2

$\sum_k k\binom{n}{k}^2$ and $n\binom{2n-1}{n-1}$ both count

The number of ways you can arrange $n$ black balls, $n-1$ white balls and $1$ red ball in two rows of $n$ balls each such that the red ball is in the lower row.

This is most easily seen for $n\binom{2n-1}{n-1}$ -- the factor of $n$ is for deciding where the red ball goes, and the binomial coefficient then distributes the black and white ones among the non-red places.

On the other hand, for $\sum_k k\binom{n}{k}^2$ choose, in order:

• the number of black balls in the top row. This is the $k$ summed over.
• the places in the top row that have black balls, for a factor of $\binom{n}{k}$.
• the places in the bottom row that have black balls, a factor of $\binom{n}{n-k}=\binom{n}{k}$.
• which of the remaining $k$ places in the bottom row will hold the red ball, for a factor of $k$.

Answer 3

For a combinatorial argument, imagine that you have $n$ men and $n$ women. From this group of $2n$ people you want to pick a team of $n$ people and choose one of the women on the team as captain. The two sides count the number of ways to do this. (On the lefthand side you’ll want to change one of the factors of $\binom{n}k$ to $\binom{n}{n-k}$.)