0
$\begingroup$

I know that this problem might qualify as a duplicate, but I didn't find any satisfactory answers among the similar posts.

We want to show by induction that \begin{equation} \sum_{i=0}^{n} \binom{i}{m} = \binom{n+1}{m+1} \end{equation} for all $n \geq 0$ and $m \geq 0$. In the basis step, we put $n=1$ and get \begin{align*} &\sum_{i=0}^1 \binom{i}{m} = \binom{0}{m} + \binom{1}{m} \end{align*} We see that $\binom{0}{m} = 0$ if $m = 0$ and $\binom{0}{m} = 1$ if $m > 0$. Lets first look at the case $m=0$: \begin{align*} &\sum_{i=0}^{1} \binom{i}{0} = 1 + \frac{1!}{0!1!} = 2 = \binom{2}{1} \end{align*} Thus, the equation holds for $n=1$ when $m = 0$. When $m>0$ we get \begin{align*} &\sum_{i=0}^{1} \binom{i}{m} = \binom{1}{m} = \frac{1!}{m!(1-m)!} \end{align*}

I don't know where to go from here. I want to end up with $\frac{2!}{(1+m)!(1 - m)!}$, so I tried to multiply with $\frac{(m+1)!}{(m+1)!}$, but that just got me here: \begin{align*} \sum_{i=0}^{1} \binom{i}{m}&= \frac{1}{m!(1-m)!} \cdot \frac{(m+1)!}{(m+1)!} \\ &= \frac{(m+1)}{(1-m)!(m+1)!} \end{align*}

I didn't get anywhere using Pascals rule, either. And this is just the basis step of the induction. The induction step, with $n = k+1$, seems just as difficult to me.

$\endgroup$
9
  • $\begingroup$ $\displaystyle \binom00 = \frac{0!}{0!0!} = 1$, not $0$. Not sure if that will help resolve the overall issue, though. $\endgroup$
    – user307169
    Sep 14, 2016 at 13:53
  • 2
    $\begingroup$ Have a look at: math.stackexchange.com/questions/1490794/… $\endgroup$ Sep 14, 2016 at 13:55
  • $\begingroup$ Notice that $\binom{n}{k}=0$ if $n<k$ for $n,k\in\Bbb N_0$. So $\binom{0}{m}=0$ if $m>0$. $\endgroup$
    – Masacroso
    Sep 14, 2016 at 14:04
  • $\begingroup$ The exact same question was asked before but was closed (improperly, in my opinion) as a duplicate: math.stackexchange.com/questions/1682754/… $\endgroup$
    – David K
    Sep 14, 2016 at 14:06
  • 1
    $\begingroup$ Another issue with your attempt at the proof is that you are trying to prove this for all $n\geq 0$ so... your basis should start with $n=0$ not $n=1$ (unless the argument is different for $n=0$ than for $n=1$ somehow and the $n=1$ case doesn't follow easily) $\endgroup$
    – JMoravitz
    Sep 14, 2016 at 14:08

3 Answers 3

2
$\begingroup$

An inductive proof rests entirely on Pascal's formula. Note the above formula can as well be written: $$\sum_{i=m}^n \binom{i}{m} = \binom{n+1}{m+1}\quad\text{or}\quad \binom{n+1}{m+1}=\sum_{k=0}^{n-m} \binom{n-k}{m}$$ We'll prove by induction on $l$ that, for all $l\;$ ($0\le l<n-m$): $$ \binom{n+1}{m+1}=\sum_{k=0}^{l}\binom{n-k}{m}+\binom{n-l}{m+1} \tag{1}$$

Indeed, if $l=0$, this is simply Pascal's formula.

For the inductive step, suppose formula $(1)$ is true for some $l$. We have \begin{align} \binom{n+1}{m+1}&=\binom{n}{m}+\binom{n-1}{m}+\dots+\binom{n-l}{m}+\binom{n-l}{m+1}\\ &=\binom{n}{m}+\binom{n-1}{m}+\dots+\binom{n-l}{m}+\binom{n-l-1}{m}+\binom{n-l-1}{m+1}\\ &=\sum_{k=0}^{l+1}\binom{n-k}{m}+\binom{n-l-1}{m+1}. \end{align}

Setting $l=n-m-1$, we obtain \begin{align} \binom{n+1}{m+1}&=\binom{n}{m}+\binom{n-1}{m}+\dots+\binom{m+1}{m}+\binom{m+1}{m+1}\\ &=\binom{n}{m}+\binom{n-1}{m}+\dots+\binom{m+1}{m}+\binom{m}{m}. \end{align}

$\endgroup$
0
$\begingroup$

For the inductive step, assume:

$$\sum_{i=0}^n \dbinom{i}{m} = \dbinom{n+1}{m+1}$$

Add $\dbinom{n+1}{m}$ to both sides to give:

$$\sum_{i=0}^{n+1} \dbinom{i}{m} = \dbinom{n+1}{m}+\dbinom{n+1}{m+1}=\dbinom{n+2}{m+1}$$

$\endgroup$
1
  • $\begingroup$ I see that you have suggested a synonym between (binomial-theorem) and (binomial-coefficients) tag. I wanted to let you know that there is a post on meta about this synonym. In general, I think that it is better to discuss synonyms first on meta. (As I tried to tell you before, but it is possible that my previous messages did not reach you.) $\endgroup$ Oct 22, 2016 at 15:03
0
$\begingroup$

Here is how you prove this via Induction. Let me know if you have questions on a particular step. Under the inductive step it's basically:

1) Perform induction on $n$. You could substitute $k$ for $n$ if you'd like but I did not.

2) Apply Pascal's Identity to split the sum into two sums.

3) Factor out $n+1$ from your sums since $i=n+1$ yields ${(n+1)-1 \choose m}$ on the first sum and ${(n+1)-1 \choose m-1}$ on the second sum, we can write the factors we pull out as ${n \choose m}$ and ${n \choose m-1}$.

4) Regroup

5) Apply Pascal's Identity to your two factored out terms and your two sums.

6) Apply your inductive hypothesis to $\sum_{i=0}^{n}{i\choose m}$.

7) Finally, apply Pascal's Identity one last time.

Here is the work:

Proposition. $\sum_{i=0}^n{i\choose m}={n+1\choose m+1}$ where $0\le m\le n$.

$Proof.$ We use mathematical induction.

Base Case. Let $n=0$. Then $\sum_{i=0}^{n=0}{i\choose m}= {0\choose 0}=1$ and ${n+1\choose m+1}={0+1\choose 0+1}={1 \choose1} = 1$. Thus for $n=0$ our proposition holds.

Inductive Step. Let $n\ge0$. Assume $\sum_{i=0}^n{i\choose m}={n+1\choose m+1}$. Then

$$\begin{align*}\sum_{i=0}^{n+1}{i\choose m}&=\sum_{i=0}^{n+1}{i-1\choose m}+\sum_{i=0}^{n+1}{i-1\choose m-1}\\ &={n\choose m}+\sum_{i=0}^{n}{i-1\choose m}+{n\choose m-1}+\sum_{i=0}^{n}{i-1\choose m-1}\\ &={n\choose m}+{n\choose m-1}+\sum_{i=0}^{n}{i-1\choose m}+\sum_{i=0}^{n}{i-1\choose m-1}\\ &={n+1\choose m}+\sum_{i=0}^{n}{i\choose m}\\ &={n+1\choose m}+{n+1\choose m+1}\\ &={n+2\choose m+1}\\ &={(n+1)+1\choose m+1} \end{align*} $$

It follows by mathematical induction that $\sum_{i=0}^n{i\choose m}={n+1\choose m+1}$ where $0\le m \le n$. $\Box$

$\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.