0
$\begingroup$

This question already has an answer here:

Prove that $$\sum_{k = 0}^n k\binom nk^2 = n \binom{2n-1}{n-1}$$

I have to prove it in a combinatorically. No induction or algebra.

$\endgroup$

marked as duplicate by Potato, Dan Rust, Start wearing purple, rschwieb, Andrey Rekalo Aug 20 '13 at 19:13

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3
$\begingroup$

Since you "have to prove it", I will assume this is some sort of homework, and give you a hint rather than a complete answer.

Can you argue combinatorially that:

  • $\displaystyle k \binom n k = n \binom{n-1}{k-1}$; and
  • $\displaystyle \sum_{k=0}^n \binom{n-1}{k-1}\binom n k = \binom{2n-1}{n-1}$?

Given these two ingredients, I'm confident you can conclude.

$\endgroup$
3
$\begingroup$

HINT: Imagine that you have a group of $n$ women and $n-1$ men. From this group you’re to choose a team of $n$ people and appoint one of them to be the team captain. It should be pretty clear that the righthand side gives the number of ways to do this, so you need only figure out why the lefthand side does so as well. You may find it useful to recall (or prove, if you’ve not seen it before) that

$$k\binom{n}k=n\binom{n-1}{k-1}\;,$$ so that

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

$\endgroup$

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