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!
On
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!
See if you can fill in the details of one (or more) of these methods.
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$