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