Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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}$$

share|cite|improve this question

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,


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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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