Prove this sum of binomial terms using induction.

Here's the problem stumping me today:

Let $n \in \mathbb{N}$ and $r \in \mathbb{N}$ such that $r \leq n$, and prove using induction that $\binom{n+1}{r+1} = \sum\limits_{i=r}^n \binom{i}{r}$.

I've setup the basics of my inductive proof, but I'm struggling with the induction step.

Could anyone point me in the right direction?

Answer

When choosing r+1 items from a set of n+1 items either you (a) choose the n+1 item (and choose the remaining r items from the first n) or (b) choose all r+1 items from the first n.

That means we can write C(r+1, n+1) = C(r, n) + C(r+1, n)

By induction (on n) C(r+1, n) = SUM[i = r...n-1] C(r, i). Including the C(r, n) we get the desired result.