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.

  • $\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 '16 at 13:53
  • 2
    $\begingroup$ Have a look at: math.stackexchange.com/questions/1490794/… $\endgroup$ – StubbornAtom Sep 14 '16 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 '16 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 '16 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 '16 at 14:08

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}

| cite | improve this answer | |

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}$$

| cite | improve this answer | |
  • $\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$ – Martin Sleziak Oct 22 '16 at 15:03

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$

| cite | improve this answer | |

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.