Hi all,

I have been given the definition for the binomial coefficient as:

$\displaystyle (n, k) = \frac{n!}{k!(n-k)!} = \frac{n(n-1)...(n-k+1)}{k!} $

(NOTE: I have written it as (n,k) because I'm not sure how to format it properly using Latex like it is seen in the textbook, with the n above the k. If anyone knows how to do this please let me know).

Now, I am asked to prove that $\displaystyle (n+1, k) = (n, k-1) + (n,k)$.

Let $\displaystyle S = n(n-1)...(n-k+1)$, then $\displaystyle (n, k-1) = \frac{S}{(k-1)!} = \frac{kS}{k!} $.

Also, $\displaystyle (n,k) = \frac{S}{k!} $

Adding them together gives: $\displaystyle \frac{(k+1)S}{k!} $.

Now, $\displaystyle (n+1,k) = \frac{(n+1)n...(n-k+2)}{k!}$

So to prove that $\displaystyle (n+1, k) = (n, k-1) + (n,k)$ I need to show:

$\displaystyle (k+1)[n(n-1)...(n-k+1)] = (n+1)n...(n-k+2)$

At this point I know I have done something wrong, because I tried it out with real values (say n=6 and k=3), and they don't match:

$\displaystyle 4(6 \cdot 5 \cdot 4) \neq (7 \cdot 6 \cdot 5)$

Can anyone help?

Thanks in advance