Take the 2-minute tour ×
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.

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|improve this question

1 Answer 1

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}\;.$$

share|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

Your Answer

 
discard

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.