# Validity of Induction for a Summation

To prove the binomial identity $$\sum_{m=k}^{n-1}\binom{m}{k} = \binom{n}{k+1}$$ will an inductive method on $n-1$ be valid?

Specifically, if we prove the base case where $n-1 = 0$, to determine it will hold for $0\leq k\leq0$

$$\sum_{m=k}^0\binom{m}{k} = \begin{cases} 1 &\mbox{if } k=0 \\ 0 &\mbox{if }k>0 \end{cases}$$

and we know that on the right-hand side $\binom{1}{k}$ will produce the same results case-wise.

Then we take the hypothesis that it holds for $0\leq k \leq n-2$, where $n-2 >0$ $$\sum_{m=k}^{n-2}\binom{m}{k} = \binom{n-1}{k+1}$$

And finally if we use this assumption to finish the inductive step, proving it holds for $0\leq k\leq n-1$ $$\sum_{m=k}^{n-1}\binom{m}{k} = \sum_{m=k}^{n-2}\binom{m}{k} + \binom{n-1}{k}$$ which by Pascal's rule gives the final result $$\binom{n-1}{k+1} +\binom{n-1}{k} = \binom{n}{k+1}$$

Does this abide by the logic of induction?

• is k a fixed number? And m iterates from k to n-1, right? Commented Feb 27, 2015 at 1:44
• k is a fixed number, and yes m iterates between those values. Commented Feb 27, 2015 at 1:47
• I'll asume you mean that $n$ is fixed in the first sum, and that $k$ can take any value $0, \cdots , n$. In the next-to-last step I think you need to consider the case $k=n-1$ separately, because that is not covered in your induction hypothesis, since $k=n-1>n-2$. Note that this case is quite trivial. Also, doing induction on $n-1$ is essentially the same as doing it on $n$, but its probably tidier to do it on $n$. Or otherwise put $r=n-1$ and do induction on $r$. Commented Feb 27, 2015 at 1:48
• Would I need to consider any extra cases if I did the induction on n? That would be straight-forward 3-step induction right? Commented Feb 27, 2015 at 1:51
• And can k have a value bigger than n? Commented Feb 27, 2015 at 1:57

We'll look at the case when $k<n$, since in all other cases both sides are zeroes.

I would recommend you to do the induction on $n$. Then if it holds for $n-1$ use induction that it holds for $n$, while $0\le k \le n-2$ and look at the case $k=n-1$ separately, since the inductive hypothesis doesn't cover that case. Here's a little help

Induction Base Let $n=1$, then we have $k=0$, which gives us:

$$\sum_{m=0}^0 \binom{m}{0} = \binom{1}{1}$$

Which is true since boths sides are 1.

Induction Hypothesis

Let the equality holds for $0\le n \le s-1$, while $0\le k < n$

Inductive Step

We'll know prove that it holds for $n=s$. We'll check 2 separate cases:

Case 1: $0\le k<s-1$

This makes sure that the inductive step is covered by the hypothesis. So now we have:

$$\sum_{m=k}^{s-1} \binom{m}{k} = \binom{s}{k+1}$$ $$\sum_{m=k}^{s-2} \binom{m}{k} + \binom{s-1}{k} = \binom{s}{k+1}$$

Now use the hypothesis and we have:

$$\binom{s-1}{k+1} + \binom{s-1}{k} = \binom{s}{k+1}$$

which hold from the Pascal's rule.

Case 2: $k=s-1$

The equality now looks like:

$$\sum_{m=s-1}^{s-1} \binom{m}{s-1} = \binom{s}{s-1+1}$$ $$\binom{s-1}{s-1} = \binom{s}{s} = 1$$

Hence the proof.

Note that you can use the fact that if $k\ge n$ both sides are zeroes and extend the equality to $k\in \mathbb{N}_0$ so you wouldn't have to check different cases, since they will all be covered by the hypothesis. But I wanted to give you a nice, more formal proof that you can use in other problems, since you may find an equality that doesn't hold for all fixed numbers in $\mathbb{N}_0$