# 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!

• It's induction on $r$. You don't need to induct on $n$. Start with $r=0$. Feb 25, 2015 at 3:22

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$

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.