Closed form sum for the series given below?

Question

Does the following series have a closed form sum?

$$f(n,r) = \sum_{i=0}^n \binom{r+i}{r}$$

Answer 1

Pascal's Identity states that $\dbinom{r+i}{r} + \dbinom{r+i}{r+1} = \dbinom{r+i+1}{r+1}$.

Hence, $\displaystyle\sum_{i = 1}^{n}\dbinom{r+i}{r} = \sum_{i = 1}^{n}\left[\dbinom{r+i+1}{r+1} - \dbinom{r+i}{r+1}\right]$.

This sum telescopes to $\dbinom{r+n+1}{r+1} - \dbinom{r+1}{r+1} = \dbinom{r+n+1}{r+1} - 1$.

Now, add $\dbinom{r}{r} = 1$ to get $\displaystyle\sum_{i = 0}^{n}\dbinom{r+i}{r} =\dbinom{r+n+1}{r+1}$.

Note: This is commonly referred to as the Hockey-Stick Identity.

Answer 2

Pascal's identity is the easiest way to verify that $\displaystyle\sum_{i = 0}^{n}\dbinom{r+i}{r} =\dbinom{r+n+1}{r+1}$,

but another way to see this is to show that the lefthand side counts the number of ways

to select $r+1$ elements from the set $\{1,2,3, \cdots, r+n+1\}$:

---

If we let $j$ be the largest integer chosen, so $r+1\le j\le r+n+1$, then we must choose $r$ additional integers from the set $\{1,2,3,\cdots,j-1\}$, and there are $\dbinom{j-1}{r}$ ways to do this.

Therefore $\displaystyle\sum_{j=r+1}^{r+n+1}\dbinom{j-1}{r}=\dbinom{r+n+1}{r+1}$, so letting $i=j-r-1$ gives

$\displaystyle\sum_{i=0}^{n}\binom{r+i}{r}=\binom{r+n+1}{r+1}$.