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

Question

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.

Answer 1

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}$

Answer 2

Hint: Use Pascal's triangle identity $$ {n+1 \choose m+1} + {n+1 \choose m} = {n+2 \choose m+1} $$ and induction.