# Sums of Binomial Coefficients - proof by induction

• Jan 22nd 2010, 05:06 AM
shmounal
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}$
• Jan 22nd 2010, 06:27 AM
Hello shmounal

Welcome to Math Help Forum!
Quote:

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.