0
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How is this combinatorial? $\endgroup$ – Al Jebr Sep 30 '15 at 2:30
  • $\begingroup$ I suppose this is combinatorial in the sense that it would be acceptable in a combinatorics journal. $\endgroup$ – William Stagner Sep 30 '15 at 2:39
  • $\begingroup$ Usually combinatorial proof means double counting. $\endgroup$ – Al Jebr Sep 30 '15 at 2:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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