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.
What I think:
On the left hand side..
$$\sum_{k=0}^n k{n \choose k}^2 = \sum_{k=0}^n k{n \choose k}{n \choose k} =\sum_{k=0}^n { k }\underbrace{{n \choose k}{n \choose n – k}}_{\text{${n\choose k}$ is equal to ${n\choose n-k}$}}$$
This is an application of the "choosing the complement identity" ${n\choose k} = {n\choose n-k}$.
$$\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}$$
${k}$ represents the number of people selected from the "President-Eligible" group of n people. If there are ${k}$ people selected from this group, there must be ${n-k}$ people selected from the second group (since the number of people selected in the final group is n.) The left hand side sums up the cases for ${k}$.
The right hand side multiplies the possibilities for "president" with possibilities for "group members".
One point of confusion I had is that I thought it should be (${n{2n \choose n}}$). But then I related this to the idea that when you use the multiplication rule to find the number of ice cream possibilities, the cone choices (president choices) are separate from the flavor choices (group member choices)! So, the president should not be counted in the group member choices. (let me know if this is the correct way to think about it). But what I'm confused about is why we don't take that into account on the left hand side $k$ possibilities for president is multiplied by ${n \choose k}$ possibilities for members.. so the 'president' is double counted as a member..?
Best Answer
I recognize my MathJax from the first time you asked this question!
For the RHS: One person is chosen a president; there are $n$ choices for President, as the group with President eligible people has $n$ members. Then across both groups there are now $(n-1) + n = 2n - 1$ people left from whom we must pick the rest of the committee. That is, choose $n-1$ people from $2n - 1$. Hence the total number of possible committees is
$$n{2n -1 \choose n-1}$$
For the LHS: Suppose $k$ people are chosen from the Presidential eligible group. Then the total ways of choosing all $n$ committee members is $\displaystyle {n \choose k}{n \choose n-k}$. Of that selection there are $k$ ways of choosing the President. Hence in this case, there are
$$ k {n \choose k}{n \choose n-k}$$ ways of composing the committee.
This doesn't double-count, it's completing the specification that the committee of $n$ people already selected have a President. This is different than the expression on the RHS where we first choose a President and then the rest of the committee. Here on the LHS we first choose the committee and then the President.
One final technical note: in the sum $\sum_{k=0}^n$ there is the case $k=0$ where there are no committee members from the Pres eligible group. In which case this is not a valid committee. But as $k=0$ the expression $k {n \choose k}{n \choose n-k}$ is also equal to zero.