6
$\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.

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..?

$\endgroup$
  • $\begingroup$ What is a "story proof"? A combinatorial proof? $\endgroup$ – Zubin Mukerjee Nov 28 '14 at 15:13
  • $\begingroup$ Yes, but I meant that you don't have to show it algebraically, just but explaining it with an example. $\endgroup$ – larrysummersstatistics Nov 28 '14 at 15:24
  • $\begingroup$ math.stackexchange.com/questions/312920/… $\endgroup$ – r9m Nov 28 '14 at 15:28
  • $\begingroup$ Thanks. So why is it that $\sum_{k=1}^nk{n\choose k}^2=n{2n-1\choose n}$ (from the suggested link) when $\sum_{k=0}^nk{n\choose k}^2=n{2n-1\choose n-1}$ and the LHS's are the same? $\endgroup$ – larrysummersstatistics Nov 28 '14 at 15:52
  • 1
    $\begingroup$ As $2n - 1 = n + (n -1)$, then $${2n - 1 \choose n} = {2n - 1 \choose n - 1}$$ $\endgroup$ – Simon S Nov 28 '14 at 16:00
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm still stuck on the RHS side.. why can't I think that we can also choose the committee and then the president like the LHS so.. choosing the group ${2n \choose n}$ then designating the president ${n}$, so there are $n{2n \choose n}$ ways of composing the committee? $\endgroup$ – larrysummersstatistics Nov 28 '14 at 15:35
  • $\begingroup$ Because if you first choose the committee from everyone there are indeed ${2n \choose n}$ possible committees. But now you have no idea how many of those came from the Presidential eligible group. There are not necessarily $n$ committee members eligible to be President; it could be any number from $0$ to $n$. $\endgroup$ – Simon S Nov 28 '14 at 15:37
  • $\begingroup$ Turns out they are the same. As $2n - 1 = n + (n -1)$, then $${2n - 1 \choose n} = {2n - 1 \choose n - 1}$$ $\endgroup$ – Simon S Nov 28 '14 at 16:00

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.