4
$\begingroup$

I was wondering if there is a combinatorial proof of this equation? $$\sum_{k=0}^{n}k \binom{n+k-1}{k} =n \binom{2n}{n+1}$$

$\endgroup$
7
$\begingroup$

Yes. Suppose that $P_1,P_2,\dots,P_{2n}$ are the members of an organization. We want to pick a committee of $n+1$ of these members. The one with the largest number will automatically be chairman of the committee, and we want to select one of the remaining $n$ members to be the secretary. There are $\binom{2n}{n+1}$ ways to choose the committee, and then $n$ ways to choose the secretary, so there are $n\binom{2n}{n+1}$ ways to accomplish the whole task.

Now count the committees whose chairman is $P_{n+k}$; clearly $k$ must range from $1$ through $n$. There are $\binom{n+k-1}{n-1}=\binom{n+k-1}k$ ways to choose from $\{P_1,\dots,P_{n+k-1}\}$ the $n-1$ members who aren’t the secretary, and the secretary must then be chosen from the remaining $(n+k-1)-(n-1)=k$ people, so there are $k\binom{n+k-1}k$ ways to choose the committee so that $P_{n-k}$ is chairman. Thus,

$$\sum_{k=0}^nk\binom{n+k-1}k=0+\sum_{k=1}^nk\binom{n+k-1}k=n\binom{2n}{n+1}\;.$$

$\endgroup$
  • $\begingroup$ Very nice explanation. $\endgroup$ – Michael Joyce Sep 5 '12 at 19:21
  • $\begingroup$ Very good clear concrete "story." $\endgroup$ – André Nicolas Sep 5 '12 at 21:19
  • $\begingroup$ I wonder how does this story pump up in your mind? Just experience or there is some way? $\endgroup$ – Vito Chou Apr 27 '15 at 16:11
  • $\begingroup$ @VitoChou: Mostly experience, I think. $\endgroup$ – Brian M. Scott Apr 27 '15 at 18:45

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.