I'm trying to figure out a combinatorial proof for:

$$\displaystyle \sum_{k \mathop = 0}^n \binom {r+k} k = \binom {r + n + 1} n$$

I've tried the committee counting thing, but that didn't work.


marked as duplicate by Grigory M, Community Jun 20 '15 at 10:46

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.


A combinatorial proof is by counting bit strings of length $r+n+1$ with exactly $n$ ones. There are $\binom{r+n+1}{n}$ such strings.

Such strings have $r+1$ zeros. Now count all bit strings of length $r+n+1$ with exactly $r+1$ zeros in which the last $0$ is at $(r+k+1)$-st position. Here $k \in \{0,1,\ldots,n\}$. There are exactly $\binom{r+k}{r} = \binom{r+k}{k}$ such strings. Since all possible positions for the last zero are $r+1, \ldots, r+n+1$, and since the sets of bit strings with the last zero at different positions are disjoint, this proves the given identity.


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