# How to simplify $\sum_{i=1}^{k}\binom{n + i - 1}{i}$? [duplicate]

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.

## marked as duplicate by Elaqqad, user147263, Najib Idrissi, Jack D'Aurizio, Lord_FarinApr 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.

• Hint: Pascal's Rule. – Prasun Biswas Apr 5 '15 at 12:24
• Observe that $$\sum_{i=1}^2\binom{n+i-1}i=\binom n1+\binom{n+1}2=\frac{2n+(n+1)n}2=\frac{n^2+3n}2=\binom{n+2}2-1$$ – lab bhattacharjee Apr 5 '15 at 12:25
• – punctured dusk Apr 8 '15 at 15:04

## 1 Answer

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