# How to prove $\binom{n+1}{m+1}=\binom{0}{m}+\binom{1}{m}+\dots+\binom{n}{m}$ combinatorially

How can we prove combinatorially

$$\binom{n+1}{m+1}=\binom{0}{m}+\binom{1}{m}+\dots+\binom{n}{m}$$

I can get LHS by asking: How many ways can we form an $m+1$ person committee from a group of $n+1$ people. But I can't get RHS with this question.

I think I can get RHS by asking: How many ways can we form an $m$ person committee from a group of at most $n$ people. But I can't get LHS with this question.

• – Austin Mohr Sep 30 '15 at 1:54
• The formula is false (or meaningless) . It should be:$$\binom{n+1}{m+1}=\binom{m}{m}+\binom{m+1}{m}+\dots+\binom{n}{m}.$$ – Bernard Sep 30 '15 at 1:54
• If only had a penny for each time this question has been asked. – Jorge Fernández Hidalgo Sep 30 '15 at 2:01
• On the other hand I've gained like 200 rep for this question over the years. – Jorge Fernández Hidalgo Sep 30 '15 at 2:02
• @Bernard It is the same formula under the convention that $\binom{k}{m} = 0$ for $k < m$. – Austin Mohr Sep 30 '15 at 2:08

Count how many ways to select $m+1$ people from a line of $n+1$ people, by selecting one person at some place (call it $k$), and then select $m$ people from the $k-1$ earlier in the line.
This count is $\sum\limits_{k=1}^{n+1} \binom{k-1}{m} = \sum\limits_{k=m+1}^{n+1}\binom{k-1}{m}$
Hint: Use Pascal's triangle identity $${n+1 \choose m+1} + {n+1 \choose m} = {n+2 \choose m+1}$$ and induction.