Show by induction that $\sum_{i=0}^n \binom{i}{m} = \binom{n+1}{m+1}$

Question

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.

Answer 1

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}

Answer 2

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

Answer 3

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$