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

Solution 1:

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.