3
$\begingroup$

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!

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

2 Answers 2

3
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .