Showing two definitions of a binomial coefficient are the same

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.

-
why don't you use some properties about $n!$ ? – mercio Feb 27 '11 at 13:08
Yeah, I've been looking into that. I know that 5!/4! = 1! etc, but I don't see how that can help me since we're using undefined variables. – Timo Willemsen Feb 27 '11 at 13:10
You are on the right track. However, after the line "Making denominators equal" you're making things far too complicated. The common denominator you want is $k!(n-k)!$ which you can achieve by expanding the left summand in the line before by $k$ and the right summand by $(n-k)$. This gives you $k \cdot (n-1)! + (n-k) \cdot (n-1)! = (k + n - k) \cdot (n-1)!$ in the numerator of the sum. – t.b. Feb 27 '11 at 13:21
@Timo: 5!/4! is not 1!. It is equal to 5. – user02138 Feb 27 '11 at 16:51
Ah awesome, I've got it ^^ – Timo Willemsen Feb 27 '11 at 20:35

1 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.

-
Thanks for your answer. I'm trying out if I can solve it now ;) – Timo Willemsen Feb 27 '11 at 19:14
Actually I've tried wolfram alpha to see what the lowest common denominator is. wolframalpha.com/input/… but I'm still not sure how to continue ;) – Timo Willemsen Feb 27 '11 at 19:38
To see that one of the denominator a multiple of the other one, use the fact that $$(n+1)!=(n+1)\cdot n!$$ Thus you have $$k!=k(k-1)!$$ and $$(n-k)!=(n-k)(n-k-1)!$$ Don't use wolframalpha for that! – Klaus Feb 27 '11 at 19:48