Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

Possible Duplicate:
simple binomial theorem proof

Prove that:

\begin{equation} \sum_{k=0}^n \binom{k+a}{k}=\frac{(n+a+1)!}{n! (a+1)!}, \end{equation}

where $a$ is a constant, without using induction. A probabilistic proof would be nice.

share|cite|improve this question

marked as duplicate by Brian M. Scott, Mike Spivey, Hagen von Eitzen, Chris Eagle, Brandon Carter Dec 10 '12 at 22:19

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

You’ll find both a combinatorial argument and a proof by induction at the earlier question cited above. – Brian M. Scott Dec 10 '12 at 21:15
@BrianM.Scott: And that was just yesterday! I'm not sure how I missed that. – Mike Spivey Dec 10 '12 at 21:18
@Mike: Well, I did have a slight advantage! (Good to see you back, by the way.) – Brian M. Scott Dec 10 '12 at 21:20
up vote 2 down vote accepted

Presumably $n$ and $a$ are nonnegative integers. The right side is ${n+a+1} \choose n$. Consider $n+a+1$ items, of which you want to choose $n$. At least one of the first $n+1$ must be left out. If the first item to be left out is number $n+1-k$ (where $0 \le k \le n$), then you already have chosen the first $n-k$ items, you are skipping number $n+1-k$ and you need to choose $k$ out of the remaining $n+a+1-(n+1-k) = a+k$. The number of ways to do that is ${a+k} \choose k$.

share|cite|improve this answer

A similar result can be found here. The corollary is the result you seek. The proof of the corollary is on the same page. Hope this helps.

share|cite|improve this answer

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