# Another combinatorial proof

• July 4th 2010, 08:28 AM
oldguynewstudent
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) $\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 $\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 $\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.
• July 4th 2010, 07:38 PM
kompik
Quote:

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) $\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 $\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 $\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
$\binom0m+\binom1m+\dots+\binom nm=\binom{n+1}{m+1}$.
We show that the same is true for n+1.
$\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
• July 5th 2010, 06:23 AM
chaoticmindsnsync
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 $m+1$ elements from a set with $n+1$ elements. So, you have one answer you need: $\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?