4
$\begingroup$

Prove with a combinatorial proof (story): $\displaystyle\sum_{k=0}^n k \binom n k ^2=n\binom{2n-1}{n-1}$

My attempt:

Let's make it easier to work with (it's very easy to show that identity): $\displaystyle\sum_{k=0}^n \frac kn \binom n k ^2=\binom{2n-1}{n-1}\Rightarrow \sum_{k=0}^n \binom {n-1}{k-1} \binom n k =\binom{2n-1}{n-1}$

RHS: we want to form a group of size $n-1$ from $2n-1$ people.

LHS: The group has $n$ men and $n-1$ women. We'll choose the men and women such that there will always be $1$ men more than women:

No men - no way to form such group.

$1$ person - $n=\binom {n-1} 0 \binom {n} 1$.

$3$ people - $\binom{n-1} 1\binom n 2$

...

$n$ people - $\binom{n-1} {n-1}\binom n n$

And if we sum up all the different cases we get: $\displaystyle\sum_{k=0}^n \binom {n-1}{k-1} \binom n k$

I'm not convinced with my story for the LHS, picking the groups such that there will always be $1$ men more seems too arbitrary. Also I'm pretty sure the first and last cases are wrong. Any tips on how fix it?

Note: no integrals nor use of other identities without proving them nor generating functions.

$\endgroup$
5
$\begingroup$

Left-hand side: Pick $k$ women to include, and $k$ men to exclude, to form a team of $n$ people. Choose one of the $k$ women to lead.
Right-hand side: Pick one of the $n$ women to lead. Pick $n-1$ of the other $2n-1$ people to form the team.

$\endgroup$
  • $\begingroup$ Why would it be the same if we exclude men? $\endgroup$ – shinzou Mar 20 '15 at 16:03
  • $\begingroup$ There are $n$ men and $n$ women. If the team has $n$ people and $k$ women, then $k$ men miss out. $\endgroup$ – Empy2 Mar 20 '15 at 16:05
  • $\begingroup$ Right, it's clearer to see it with: $\binom n k = \binom n {n-k}$. One more thing, could the given expression be wrong for $k=0$? $\endgroup$ – shinzou Mar 20 '15 at 16:19
  • $\begingroup$ I think $n-1\choose-1$ is defined to equal zero, which equals the corresponding term on the left-hand side. $\endgroup$ – Empy2 Mar 20 '15 at 16:25
  • $\begingroup$ I'm getting the same problem when trying to explicitly show every case of the sum: a team of 1 member is supposed to be to choose 1 women ($n$) but on the LHS we get $n^2$. $\endgroup$ – shinzou Mar 20 '15 at 16:40

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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