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.

Grandad