6
$\begingroup$

I have a homework question where we have to prove the following definitions of a binomial coefficient are equal, algebraically.

enter image description here

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.

enter image description here

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.

$\endgroup$
8
  • $\begingroup$ why don't you use some properties about $n!$ ? $\endgroup$
    – mercio
    Feb 27, 2011 at 13:08
  • $\begingroup$ 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. $\endgroup$ Feb 27, 2011 at 13:10
  • 1
    $\begingroup$ 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. $\endgroup$
    – t.b.
    Feb 27, 2011 at 13:21
  • 2
    $\begingroup$ @Timo: 5!/4! is not 1!. It is equal to 5. $\endgroup$
    – user02138
    Feb 27, 2011 at 16:51
  • 1
    $\begingroup$ Ah awesome, I've got it ^^ $\endgroup$ Feb 27, 2011 at 20:35

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks for your answer. I'm trying out if I can solve it now ;) $\endgroup$ Feb 27, 2011 at 19:14
  • $\begingroup$ 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 ;) $\endgroup$ Feb 27, 2011 at 19:38
  • $\begingroup$ 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! $\endgroup$
    – Klaus
    Feb 27, 2011 at 19:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .