3
$\begingroup$

How to simplify $\sum_{i=1}^{k}\binom{n + i - 1}{i}$? I tried reducing the sum to $\binom{n}{1}, \binom{n}{2}, \binom{n}{3}$ and so on but couldn't get a pattern.

$\endgroup$

marked as duplicate by Elaqqad, user147263, Najib Idrissi, Jack D'Aurizio, Lord_Farin Apr 11 '15 at 14:45

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.

4
$\begingroup$

The problem becomes trivial on using Pascal's Rule. Using it, we have,

$$\binom{n+i-1}{i}=\binom{n+i}{i}-\binom{n+i-1}{i-1}$$

Now, substituting this into our required sum (say $S$) gives us a telescoping sum (the middle terms gets cancelled out).

$$S=\sum_{i=1}^k \binom{n+i-1}{i}=\sum_{i=1}^k \left\{\binom{n+i}{i}-\binom{n+i-1}{i-1}\right\}\\ \implies S=\binom{n+1}{1}-\binom{n}{0}+\binom{n+2}{2}-\binom{n+1}{1}+\ldots +\binom{n+k}{k}-\binom{n+k-1}{k-1}\\ \implies S=\binom{n+k}{k}-\binom{n}{0}\\ \implies \boxed{S=\dbinom{n+k}{k}-1}$$

$\endgroup$

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