Show that $\binom{n+1}{r} = \binom{n}{r} +\binom{n}{r-1}$ for $1 ≤ r ≤ n$.

Question

I've found many ways of proving $\binom{n}{r} = \binom{n-1}{r} +\binom{n-1}{r-1}$ However I can't find any for proving that:

$$\binom{n+1}{r} = \binom{n}{r} +\binom{n}{r-1}\;\text{ for }1 ≤ r ≤ n.$$

When I expand the equation it comes out to this:

$$\frac{(n+1)!}{(n-r+1)!r!}= \frac{n!}{(n-r)!r!}+\frac{n!}{(n-(r-1))!(r-1)!}$$

I'm not sure where to go from here. Can anyone help?

Answer 1

$$C(n, r) + C(n, r − 1)=\frac{n!}{(n-r)!r!}+\frac{n!}{(n-r+1)!(r-1)!}=\frac{n!(n-r+1)+n!r}{(n-r+1)!r!}=\frac{(n+1)!}{(n-r+1)!r!}=C(n + 1, r) $$

Answer 2

Just make the mapping $n \mapsto n+1$ in your original identity. Or, if that's a bit too hard to understand, simply let $n=k+1$. The desired form appears immediately.

Put another way, the two identities are equivalent.

Answer 3

A selection of $r$ from $n+1$ items in a line either includes the first item and $r-1$ from the remaining $n$, or does not include the first item and all $r$ are from the rest.   Therefore: $$\binom {n+1}{r}=\binom{1}{1}\binom{n}{r-1}+\binom 10\binom nr$$