Problem involving mathematical induction

[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

 

[FactChecker]

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).

 

[issacnewton]

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

 

[nuuskur]

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

 

[FactChecker]

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".

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).

 

[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$.

 

[WWGD]

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

 

[Office_Shredder]

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

 

[WWGD]

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

 

[issacnewton]

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.

 

[haruspex]

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.