Thread: Sums of Binomial Coefficients - proof by induction

1. Sums of Binomial Coefficients - proof by induction

Hi,

Was wondering if anyone could help with this question i've been struggling with. Im sure I'm just missing something simple but can't work it out. I need to prove by induction that the sum from j=o to n of j Choose k is equal to n+1 Choose k+1. Think I need to use the identity n Choose k+1 is equal to (n-1 Choose k) plus (n-1 choose k+1). Any help very appreciated!!

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

2. Hello shmounal

Welcome to Math Help Forum!
Originally Posted by shmounal
Hi,

Was wondering if anyone could help with this question i've been struggling with. Im sure I'm just missing something simple but can't work it out. I need to prove by induction that the sum from j=o to n of j Choose k is equal to n+1 Choose k+1. Think I need to use the identity n Choose k+1 is equal to (n-1 Choose k) plus (n-1 choose k+1). Any help very appreciated!!

$\displaystyle \binom{n+1}{k+1} = \sum_{j=0}^{n}\binom{j}{k}$
You're right! The result you quote is:
$\displaystyle \binom{n-1}{k}+\binom{n-1}{k+1}= \binom{n}{k+1}$
and if, in this result, we replace $\displaystyle n$ by $\displaystyle (n+2)$ we get:
$\displaystyle \binom{n+1}{k}+\binom{n+1}{k+1}= \binom{n+2}{k+1}$ ...(1)
Now suppose that $\displaystyle P(n)$ is the propositional function
$\displaystyle \sum_{j=0}^{n}\binom{j}{k}= \binom{n+1}{k+1}$
Then:
$\displaystyle P(n) \Rightarrow$
$\displaystyle \sum_{j=0}^{n+1}\binom{j}{k}= \sum_{j=0}^{n}\binom{j}{k}+\binom{n+1}{k}$
$\displaystyle =\binom{n+1}{k+1}+ \binom{n+1}{k}$

$\displaystyle =\binom{n+2}{k+1}$ using
(1)
Therefore:
$\displaystyle P(n) \Rightarrow P(n+1)$
I'll leave you to verify that $\displaystyle P(1)$ is true, and that by Induction the result follows.