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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.