We show that the same is true for n+1.
See Sum of k Choose m up to n - ProofWiki
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.
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 . 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
I can get no further.
Can someone help or tell me if I have the whole combinatorial proof thing wrong.
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 elements from a set with elements. So, you have one answer you need: . 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?