1. Another combinatorial proof

Give combinatorial or bijective proofs of the following. Part of your job is to determine all values of n,k, and/or m for which the identities are valid.

c) $\displaystyle \left({0\atop m}\right)+\left({1\atop m}\right)+\left({2\atop m}\right)+\ldots+\left({n\atop m}\right)=\left({n+1\atop m+1}\right)$

I can't get very far with this one either. I notice that all terms on the left hand side are zero until we get to $\displaystyle \left({m\atop m}\right)$. Then I calculate all terms equal 1, so we have n-m terms which makes the left hand side equal n-m.

The right hand side I get $\displaystyle \frac{(n+1)!}{(m+1)!(n+1-m-1)!}=\frac{(n+1)!}{n!(m+1)}=\frac{n+1}{m+1}$

I can get no further.

Can someone help or tell me if I have the whole combinatorial proof thing wrong.

2. Originally Posted by oldguynewstudent
Give combinatorial or bijective proofs of the following. Part of your job is to determine all values of n,k, and/or m for which the identities are valid.

c) $\displaystyle \left({0\atop m}\right)+\left({1\atop m}\right)+\left({2\atop m}\right)+\ldots+\left({n\atop m}\right)=\left({n+1\atop m+1}\right)$

I can't get very far with this one either. I notice that all terms on the left hand side are zero until we get to $\displaystyle \left({m\atop m}\right)$. Then I calculate all terms equal 1, so we have n-m terms which makes the left hand side equal n-m.

The right hand side I get $\displaystyle \frac{(n+1)!}{(m+1)!(n+1-m-1)!}=\frac{(n+1)!}{n!(m+1)}=\frac{n+1}{m+1}$

I can get no further.

Can someone help or tell me if I have the whole combinatorial proof thing wrong.
Use induction. Inductive step: Suppose that
$\displaystyle \binom0m+\binom1m+\dots+\binom nm=\binom{n+1}{m+1}$.
We show that the same is true for n+1.
$\displaystyle \binom0m+\binom1m+\dots+\binom nm+\binom{n+1}m=\binom{n+1}{m+1}+\binom{n+1}m=\bin om{n+2}{m+1}$.

See Sum of k Choose m up to n - ProofWiki

3. Remember that the point of a combinatorial proof is that they are easier to write than simply grinding out the identity, as you seem do be doing. In a combinatorial proof, you have to ask a question, and then answer it by counting it in two different ways.

Therefore, consider this.

Remember, the RHS basically is asking the number of ways to choose $\displaystyle m+1$ elements from a set with $\displaystyle n+1$ elements. So, you have one answer you need: $\displaystyle \binom{n+1}{m+1}$. Now on the left hand side, you have a sum. What does that imply? Or in other words, what conditions must you apply to get a sum?