# Sums of Binomial Coefficients - proof by induction

• Jan 22nd 2010, 06: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!!

$\binom{n+1}{k+1} = \sum_{j=0}^{n}\binom{j}{k}$
• Jan 22nd 2010, 07: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!!

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

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

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