I have a homework question where we have to prove the following definitions of a binomial coefficient are equal, algebraically.
This is what I got so far, and it's getting pretty complicated. And I could use some directions on how to continue. At the moment I think I'm just doing it wrong from the start and I'm overcomplicating things. But I'm not quite sure how to continue, because I'm just staring at these numbers and can't continue.
I have writting this in Microsoft Word, so I'll use images to show what I've got so far, because writing this all again in Latex is tedious.
Also this is homework for me, so please don't give me the answer yet, because I know I could just look this up on the internet. I'd like to prove it myself for most of the part, but since I'm stuck I was wondering if someone could give me a slight hint on what to do.
Best Answer
You were on the right track, but you haven't chosen the easiest/lowest common denominator.
As you've written,
$${{n-1} \choose {k-1}}+{{n-1} \choose k}=\frac{(n-1)!}{(n-k)!(k-1)!}+\frac{(n-1)!}{(n-k-1)!k!}$$
Isn't one of the denominator a multiple of the other one ?
Remember that $(n+1)!=(n+1)\cdot n \cdots 2\cdot 1=(n+1)\cdot n!$.
Note that you can also prove this using a combinatorial proof, which will give you a more intuitive idea of why the equality holds.