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}$
Combinatorial proof of an equation
1 Answers
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}\;.$
-
0@VitoChou: Mostly experience, I think. – 2015-04-27