Sum of combinations with varying $n$ [duplicate]

What is the sum of number of ways of choosing $n$ elements from $(n+r)$ elements where $r$ is fixed and $n$ varies from $1$ to $m$ ? Can this be reduced to a formula ?

$$\sum ^m _{n=1} \binom{n + r}n$$

marked as duplicate by punctured dusk, user147263, Najib Idrissi, Aaron Maroja, Jack D'AurizioApr 8 '15 at 15:56

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.

2 Answers

Yes your formula is corrct and: $$\sum_{n=1}^m \dbinom{n+r}n=\sum_{n=1}^m\dbinom{n+r}{r}$$

and you can prove by induction that this $\dbinom{m+r+1}{r+1}-1$

This is a combinatorial proof of the identity.

The number of ways to select $m+1$ items out of $n+m+1$ is $\binom{n+m+1}{m+1} = \binom{n+m+1}{n}$. Sets of size $n$ are $\mathcal{S}=(a_0, a_1 \ldots a_{n-1}), (a_1, a_2 \ldots a_{n}), \ldots ,(a_{m+1}, a_{m+2} \ldots a_{m+n}).$

Let's split the number of ways to select $n$ elements if the smallest element in $\mathcal{S}$ is $a_0$: this is clearly $\binom{n+m}{n-1}$, if it's $a_1$: $\binom{n+m-1}{n-1}$, etc. Finally, if it's $a_{m+1}$, the number is just $\binom{n-1}{n-1}$. But this is clearly equivalent to the total number of ways to select $\binom{n+m+1}{n}$, we just split this number based on the smallest element in the subset. Hence, $$\binom{n+m+1}{n} = \sum_{k=0}^{m} \binom{n+k}{n}$$