0
$\begingroup$

Give a story proof that

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

Consider choosing a committee of size n from two groups of size n each , where only one of the two groups has people eligible to become president.

So I think the left side represents the number of ways to choose groups when you have k = 1,2,3...people chosen from the "president-eligible" group, and the rest from the other group, and then sums up the possibilities. On the right hand side, n people are eligible to become president, and then you choose the rest of the group members? Or something like that? What is the best interpretation? Thanks.

What is the connection with Vandermonde's identity? (this was suggested on another post with a similar proof)

$\endgroup$
  • $\begingroup$ $\sum_{k=0}^n\binom{n}k^2=\binom{2n}n$ is a special case of Vandermonde’s identity; both it and the full identity have combinatorial proofs similar to the one that you’re working on here. $\endgroup$ – Brian M. Scott Nov 28 '14 at 19:49
1
$\begingroup$

Hint:

$$\sum_{k=0}^n k{n \choose k}^2 = \sum_{k=0}^n \underbrace{ k \ \ \ {n \choose k}}_{\text{Pres eligible group}}{n \choose n - k}$$

$\endgroup$
0
$\begingroup$

HINT: Try to adapt this combinatorial proof of the very similar identity

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

$\endgroup$
  • $\begingroup$ I edited the questions with my interpretation based on the proof you provided; is it a good interpretation? $\endgroup$ – larrysummersstatistics Nov 28 '14 at 14:25
  • $\begingroup$ @larrysummersstatistics: It’s close. I would first rewrite it as $k\binom{n}k\binom{n}{n-k}$. Then $\binom{n}k$ is the number of ways to choose $k$ from the president-eligible group, $k$ is the number of ways to pick one of those $k$ to be president, and $\binom{n}{n-k}$ is the number of ways to fill out the committee with $n-k$ people from the non-eligible group. Then, as you say, you sum over the possible values of $k$. On the right, $n$ is the number of ways to choose the president, and $\binom{2n-1}{n-1}$ is the number of ways to choose the rest of the committee. $\endgroup$ – Brian M. Scott Nov 28 '14 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.