2
$\begingroup$

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.

$\endgroup$

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.

1
$\begingroup$

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.

$\endgroup$

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