# Combinatorial proof of an equation

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

## 1 Answer

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

• 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