# Thread: Binomial coefficient proof - where have I gone wrong in my working?

1. ## Binomial coefficient proof - where have I gone wrong in my working?

Hi all,

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

$(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 $(n+1, k) = (n, k-1) + (n,k)$.

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

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

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

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

$(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:

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

Can anyone help?

$\binom{n}{k-1}+\binom{n}{k} = \frac{n!}{(k-1)!(n-k+1)!}+\frac{n!}{k!(n-k)!}$

And take this over a common denominator.

3. Btw! For ${n\choose k}$ you can write {n \choose k}.

4. Originally Posted by mrfour44
Btw! For ${n\choose k}$ you can write {n \choose k}.
Alternately, $$\binom{N}{k}$$ gives $\binom{N}{k}$

5. Originally Posted by TheCoffeeMachine
$\binom{n}{k-1}+\binom{n}{k} = \frac{n!}{(k-1)!(n-k+1)!}+\frac{n!}{k!(n-k)!}$