Problem involving mathematical induction

AI Thread Summary
The discussion centers on proving the statement $$ \sum_{k=0}^{n} \binom{k}{r} = \binom{n+1}{r+1} $$ using mathematical induction. The base case for n=1 is established, confirming the equality holds. The challenge arises in formulating the induction step for P(m+1), where participants clarify that the correct form is $$ \sum_{k=0}^{m+1} \binom{k}{r} = \binom{m+2}{r+1} $$, with the range of r adjusted accordingly. The proof is completed by applying the binomial coefficient recurrence relation, demonstrating that the induction hypothesis holds for all natural numbers n. The discussion concludes with a consensus on the validity of the proof while acknowledging alternative combinatorial interpretations.
issacnewton
Messages
1,035
Reaction score
37
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
 
Physics news on Phys.org
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##

<br /> \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}.<br />
Now figure out if and why this is equal to the required quantity. Additionally, what happens when ##r=n+1##?
 
Last edited:
  • Like
Likes 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:
  • Like
Likes 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
 
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! ;).
 
  • Haha
Likes 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
 
  • #10
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##.
 
  • #11
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.
 
  • #12
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.
 

Similar threads

Back
Top