Problem involving mathematical induction

• issacnewton
issacnewton
Homework Statement
Prove that ## \sum_{k=0}^{n} \binom{k}{r} = \binom{n+1}{r+1} ## where ##1 \leq r \leq n##
Relevant Equations
Mathematical Induction
Here is my attempt. Let ##P(n)## be the statement

$$\sum_{k=0}^{n} \binom{k}{r} = \binom{n+1}{r+1}$$

where ##1 \leq r \leq n##. Now base case is ##n = 1##. For this, we have

$$\sum_{k=0}^{1} \binom{k}{r} = \binom{0}{r} + \binom{1}{r}$$

Since ##1 \leq r \leq 1##. It means that ##r = 1##. With this, above expression evaluates to

$$\sum_{k=0}^{1} \binom{k}{r} = \binom{0}{r} + \binom{1}{r} = \binom{0}{1} + \binom{1}{1}$$

$$\sum_{k=0}^{1} \binom{k}{r} = \binom{0}{1} + \binom{1}{1} = 0 + 1 = 1$$

And, we have on right hand side,

$$\binom{1+1}{1+1} = 1$$

Since both sides match, ##P(1)## is true. Now, let ##m \geq 1 ## be an arbitrary in ##\mathbb{N}##. Suppose that ##P(m)## is true. i.e.

$$\sum_{k=0}^{m} \binom{k}{r} = \binom{m+1}{r+1}$$

where ##1 \leq r \leq m##. We are supposed to prove ##P(m+1)##. But, I don't know what will be the form of ##P(m+1)##. My guess is

$$\sum_{k=0}^{m+1} \binom{k}{r} = \binom{m+2}{r+1}$$

But, this doesn't look quite right. On right hand side, we have ##m+2## in the top and ##r+1## at the bottom. And, does ## 1 \leq r \leq m+1 ## here ? I am little confused.

Thanks

issacnewton said:
We are supposed to prove ##P(m+1)##. But, I don't know what will be the form of ##P(m+1)##. My guess is

$$\sum_{k=0}^{m+1} \binom{k}{r} = \binom{m+2}{r+1}$$

But, this doesn't look quite right. On right hand side, we have ##m+2## in the top and ##r+1## at the bottom. And, does ## 1 \leq r \leq m+1 ## here ?
Don't change r in the equation. Only add one to m in the equation and the range of r to get P(m). That will automatically give r an increase in its range to ##1 \le r \le m+1##.
CORRECTION: The original P(n) already had r+1 on the right hand side, so that is ok for P(n+1).

Last edited:
So, what I have written for ##P(m+1)## is right ?. I don't understand your last sentence.

##r## is fixed between ##1## and ##n##. When you do the induction step, ##r## is fixed between ##1## and ##n+1##. The induction assumption is that said equality holds for ##n## and for every ##1\leqslant r\leqslant n##.

Regardless, you need to work out what ##\binom{k}{r}## means for ##k<r##. Naturally one would think there are zero choices of ##r> k## out of ##k##, so by induction assumption it follows that for any ##1\leqslant r\leqslant n##

$$\sum _{k=0}^{n+1} \binom{k}{r} = \sum _{k=0}^{n}\binom{k}{r} + \binom{n+1}{r} = \binom{n+1}{r+1} + \binom{n+1}{r}.$$
Now figure out if and why this is equal to the required quantity. Additionally, what happens when ##r=n+1##?

Last edited:
issacnewton
issacnewton said:
So, what I have written for ##P(m+1)## is right ?.
I disagree with the "r+1" on the right side of your equation. I think it should remain just "r".
issacnewton said:
I don't understand your last sentence.
The lower line on the right side of your equation should range from 1 to m+1. It should just be r (not r+1) from 1 to m+1. So your ##1 \le r \le m+1## is correct.
CORRECTION: The original P(n) already had r+1 on the right hand side, so that is ok for P(n+1).

Last edited:
issacnewton
Ok, so , I have to prove ##P(m+1)##, i.e.

$$\sum_{k=0}^{m+1} \binom{k}{r} = \binom{m+2}{r+1}$$

where ##1 \leq r \leq m+1##. We have

$$\sum_{k=0}^{m+1} \binom{k}{r} = \sum_{k=0}^{m} \binom{k}{r} + \binom{m+1}{r}$$

Using ##P(m)## here

$$\sum_{k=0}^{m} \binom{k}{r} + \binom{m+1}{r} = \binom{m+1}{r + 1} + \binom{m+1}{r}$$

Now, we use a recurrence relation for the binomial coefficient.

$$\binom{m+1}{r + 1} + \binom{m+1}{r} = \binom{m+2}{r + 1}$$

This proves that

$$\sum_{k=0}^{m+1} \binom{k}{r} = \binom{m+2}{r + 1}$$

where ##1 \leq r \leq m+1##. This means that ##P(m+1)## is true. Since ##m \geq 1## is arbitrary, we have

$$\forall \; m \geq 1 \bigl[ P(m) \rightarrow P(m+1) \bigr]$$

Hence, using, mathematical induction, we have, for all ##n \in \mathbb{N}##

$$\sum_{k=0}^{n} \binom{k}{r} = \binom{n+1}{r+1}$$

where ##1 \leq r \leq n##. I hope this is valid proof.

Thanks

nuuskur
The induction assumption applies for ##1\leqslant r\leqslant m##. In the event ##r=m+1##, we have the identity ##1=1##.

It's called (Isaac)Newton's Binomial for a reason! ;).

issacnewton
Were you required to use induction to prove this? Many identities like this have natural combinatorial interpretations (and the combinatorics is often how they were first discovered), and this one has a good combinatorial two line proof

I'm confused on whether we're supposed to iterate over ##r## or show that the result holds for all ##r## integers ##1,2,..,n##.

The problem is given in the book called Book of Proof which is available online as PDF. I am aware that this can be proven using combinatorics. But there, author wants us to use mathematical induction.

WWGD said:
I'm confused on whether we're supposed to iterate over ##r## or show that the result holds for all ##r## integers ##1,2,..,n##.
The latter.

WWGD

• Calculus and Beyond Homework Help
Replies
15
Views
1K
• Precalculus Mathematics Homework Help
Replies
10
Views
453
• Calculus and Beyond Homework Help
Replies
6
Views
641
• Precalculus Mathematics Homework Help
Replies
2
Views
1K
• Precalculus Mathematics Homework Help
Replies
7
Views
977
• Precalculus Mathematics Homework Help
Replies
5
Views
1K
• Precalculus Mathematics Homework Help
Replies
1
Views
947
• Precalculus Mathematics Homework Help
Replies
11
Views
296
• Precalculus Mathematics Homework Help
Replies
7
Views
1K
• Precalculus Mathematics Homework Help
Replies
4
Views
2K