Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
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. –  t.b. Feb 27 '11 at 13:21
2  
@Timo: 5!/4! is not 1!. It is equal to 5. –  user02138 Feb 27 '11 at 16:51
1  
Ah awesome, I've got it ^^ –  Timo Willemsen Feb 27 '11 at 20:35

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.