Verify the following by mathematical induction Verify the following by mathematical induction:
$${n \choose 0} + {n+1 \choose 1} + {n+2 \choose 2} + \cdots + {n+r \choose r} = {n+r+1 \choose r}$$
I need some help with this proof...I understand induction, but I am having trouble using it for this combinatorial identity.
Do I start with $n=1$ or $n=r=1$? And how would the induction hypothesis work?
Any help or suggestions would be great! Thanks in advance!
 A: Consider the following "more conventional" statement (adjust notation accordingly) of the problem: 
Problem: Show that for each $n\geq 0$,
$$
\sum_{i=0}^n\binom{m+i}{i}=\binom{m+n+1}{n}.
$$
Proof: For each $n\geq 0$, let $S(n)$ be the declaration that for every $m\geq 0$,
$$
\sum_{i=0}^n\binom{m+i}{i}=\binom{m+n+1}{n}.
$$
Base step: $S(0)$ says that $\sum_{i=0}^0\binom{m+i}{i}=\binom{m+1}{0}$, which is true because both sides are equal to $1$. 
Induction step: For some $k\geq 0$, assume that $S(k)$ is true. To be shown is that $S(k+1)$ is true; that is, for any $m\geq 0$,
$$
\sum_{i=0}^{k+1}\binom{m+i}{i}=\binom{m+k+2}{k+1}.
$$
Beginning with the LHS,
\begin{align}
\sum_{i=0}^{k+1}\binom{m+i}{i} &= \sum_{i=0}^k\binom{m+i}{i}+\binom{m+k+1}{k+1}\tag{defn. of $\sum$}\\[1em]
  &= \binom{m+k+1}{k}+\binom{m+k+1}{k+1}\tag{by $S(k)$}\\[1em]
  &= \binom{m+k+2}{k+1},\tag{Pascal's identity}
\end{align}
we obtain the RHS. 
By mathematical induction, then, for all $n\geq 0, S(n)$ is true. $\Box$
A: Hint for induction step: you need to show that
$$\binom{n+r+1}{r}+\binom{n+r+1}{r+1}=\binom{n+r+2}{r+1}\ .$$
There are at least three ways to do this - take your pick!


*

*Algebra - write the binomial coefficients in terms of factorials.

*Well-known identity connected with Pascal's triangle.

*Combinatorial interpretation of the binomial coefficients.


See if you can fill in the details of one (or more) of these methods.
