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.

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

2 Answers 2

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

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