- #1

issacnewton

- 1,024

- 35

- 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

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