5
$\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.

  • 0
    why don't you use some properties about $n!$ ?2011-02-27
  • 0
    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.2011-02-27
  • 1
    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.2011-02-27
  • 2
    @Timo: 5!/4! is not 1!. It is equal to 5.2011-02-27
  • 0
    @user02138 ofcourse, you're right. Actually I knew that, don't know why I said that. Thanks for the clarification.2011-02-27
  • 0
    @Theo Buehler, I'm sorry to ask this, but I couldn't find it on the internet and since english is not my main language. What exactly do you mean by 'expanding' the summands.2011-02-27
  • 0
    "Expanding a fraction $\frac{a}{b}$ by $k$" means writing $\frac{a}{b} = \frac{k\cdot a}{k \cdot b}$. You have a sum of two fractions in said equation. Expand the left one by $k$ and the right one by $(n-k)$. Sorry about the confusion.2011-02-27
  • 1
    Ah awesome, I've got it ^^2011-02-27

1 Answers 1

5

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.

  • 0
    Thanks for your answer. I'm trying out if I can solve it now ;)2011-02-27
  • 0
    Actually I've tried wolfram alpha to see what the lowest common denominator is. http://www.wolframalpha.com/input/?i=%28%28n%E2%88%92k%29%21%28k%E2%88%921%29%21%29+%2A+%28n%E2%88%92k%E2%88%921%29%21k%21%2Fgcd%28%28n%E2%88%92k%29%21%28k%E2%88%921%29%21%2C+%28n%E2%88%92k%29%21%28k%E2%88%921%29%21+%29 but I'm still not sure how to continue ;)2011-02-27
  • 0
    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!2011-02-27