Write the sum on the left as:

We can notice that the number on the RHS is the number of ways to choose r+1 numbers out of the set

The sum on the LHS can be interpreted like this:

If we know that the greatest number we will choose is r+k (for

), then we can choose the rest of the numbers in ways. If we sum all those values for all different values of k between 1 and n-r+1, we will get the total number of ways to choose r+1 numbers from the set mentioned before.But, we also know that that will be the sum on the RHS, so the RHS and the LHS must be equal!

]]>(Expand LHS and show it's equal to RHS.) Hence

Adding up

Rearrange, noting that

, and you're done.]]>in algebra?]]>