# Prove summation formula for binomial coefficients [duplicate]

Possible Duplicate:
simple binomial theorem proof

Prove that:

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

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

-

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

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

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