1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof of combinations

  1. Apr 23, 2013 #1
    1. The problem statement, all variables and given/known data
    Prove the following:

    [itex]\frac{n!}{m!(n-m)!} = \frac{n!}{(m-2)!(n-m + 2)!} + 2* \frac{(n-1)!}{(m-1)!(n-m)!} + \frac{(n-2)!}{(m-2)!(n-m)!} [/itex]



    3. The attempt at a solution

    I tried writing following

    [itex]\frac{n!}{m!(n-m)!} = \frac{n!}{m!(n-m)!}(\frac{m(m-1)}{(n-m + 2)(n-m + 1)} + \frac{2m}{n} + \frac{m(m-1)}{n(n-1)} [/itex])

    Now i should get [itex]\frac{m(m-1)}{(n-m + 2)(n-m + 1)} + \frac{2m}{n} + \frac{m(m-1)}{n(n-1)} = 1[/itex]
    but i dont get 1. Any other ideas?
     
  2. jcsd
  3. Apr 23, 2013 #2

    SteamKing

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper

    Hint: m! = m * (m-1) * (m-2)!
     
  4. Apr 23, 2013 #3
    I know that, but where to use it?
     
  5. Apr 23, 2013 #4

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    your m(m-1)/n(n-1) is wrong :redface:
     
  6. Apr 23, 2013 #5
    I rechecked it two or three time i really don't see how it is wrong.
     
  7. Apr 23, 2013 #6

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    What is the lowest common denominator for the right-hand side ?

     
  8. Apr 23, 2013 #7
    (m-1)!(n-m+2)!
     
  9. Apr 23, 2013 #8
    I don't understad why, since (m-2)! doesn't contain (m-1) nor (n-m)! contains (n-m+2)! or (n-m+1)!
     
  10. Apr 23, 2013 #9
    If i want get whole expression under one fraction i should multply first fraction with (m-1)/(m-1) to get n!(m-1)/(m-1)!(n-m+2)! , second fraction with (n-m+2)(n-m+1)/(n-m+2)(n-m+1) to get
    (n-1)!(n-m+2)(n-m+1)/(m-1)!(n-m+2)! , and third with (m-1)(n-m+2)(n-m+1)/(m-1)(n-m+2)(n-m+1)
    to get (n-2)!(m-1)(n-m+2)(n-m+1)/(m-1)!(n-m+2)!
     
  11. Apr 23, 2013 #10

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    You were correct. I deleted my post, but you must have seen it before I deleted it.
     
  12. Apr 23, 2013 #11

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    That's virtually unreadable as it is written. Break it up into separate lines & give it some space...

    As follows:
    If i want get whole expression under one fraction i should multiply:

    first fraction with (m-1)/(m-1) to get
    n!(m-1)/(m-1)!(n-m+2)! ,​
    second fraction with (n-m+2)(n-m+1)/(n-m+2)(n-m+1) to get
    (n-1)!(n-m+2)(n-m+1)/(m-1)!(n-m+2)! ,​
    and third with (m-1)(n-m+2)(n-m+1)/(m-1)(n-m+2)(n-m+1)
    to get
    (n-2)!(m-1)(n-m+2)(n-m+1)/(m-1)!(n-m+2)!​
    So the numerator is (m-1)n! + 2(n-m+2)(n-m+1)(n-1)! + (m-1)(n-m+2)(n-m+1)(n-2)! .

    There's a common factor of (n-2)! , right?
     
  13. Apr 23, 2013 #12
    After that i get (n-2)!*(n(n-1)(m-1) + 2(n-m+2)(n-m+1)(n-1) + (m-1)(n-m+2)(n-m+1))/(m-1)!(n-m+2)!

    i tried and i can't find any other common factor in numerator and i have common factors between two products such as (n-1) , (m-1), (n-m+2)(n-m+1). Only other way is to multiply everything and then try to factor out something that will cancel m-1 and (n-m+2)(n-m+1) in denominator.
     
  14. Apr 23, 2013 #13

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Have you checked whether it even seems to be true? Try n=m=2.
     
  15. Apr 23, 2013 #14

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    I was about to ask a similar question.

    This may also be what tiny-tim was suggesting.


    Is there a typo in your expression?

    In terms of binomial coefficients, what the OP states is that you are trying to prove that

    [itex]\displaystyle \ \binom{n}{m}=\binom {n} {m-2}+2\binom {n-1} {m-1}+\binom {n-2} {m-2}\ .[/itex]
     
  16. Apr 23, 2013 #15
    That is exactly what i need to prove, i just didn't know how to write it like that using Latex. Here is full text of problem:

    Prove that [itex]\displaystyle \ \binom{n}{m}=\binom {n} {m-2}+2\binom {n-1} {m-1}+\binom {n-2} {m-2}\ n\geq2, m \geq2 [/itex]

    When i plug in n=m=2 i get [itex]\frac{0}{0} = \frac{2}{0} + \frac{2}{0} + \frac{0}{0}[/itex]
     
  17. Apr 23, 2013 #16

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    No, 0! = 1. [itex]\binom{0}{0} = \binom{2}{0} = 1[/itex]
     
  18. Apr 23, 2013 #17
    Yea, i overlooked that. With that in mind.

    Let n=m=2

    [itex]\frac{2!}{2!(2-2)!} = \frac{2!}{(2-2)!(2-2 + 2)!} + 2* \frac{(2-1)!}{(2-1)!(2-2)!} + \frac{(2-2)!}{(2-2)!(2-2)!} [/itex]

    [itex]\frac{1}{1(0)!} = \frac{1}{(0)!1} + 2* \frac{1}{1(0)!} + \frac{(0)!}{(0)!(0)!} [/itex]

    [itex] 1 = 1 + 2 + 1 [/itex]

    [itex] 1 = 4 [/itex]
     
  19. Apr 24, 2013 #18

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Do you suppose the problem should have been to prove

    [itex]\displaystyle \ \binom{n}{m}=\binom {n-2} {m-2}+2\binom {n-2} {m-1}+\binom {n-2} {m}\,,\ n\geq2, m \geq2 \ ?[/itex]
     
  20. Apr 24, 2013 #19
    Maybe i will try to slove it,

    This problem should be difficult according to my text book, here is a pic from my textbook:

    http://img444.imageshack.us/img444/8316/img00121201304241927.jpg [Broken]
     
    Last edited by a moderator: May 6, 2017
  21. Apr 24, 2013 #20
    I managed to prove this without much problem.
    Probably it is a typo in my textbook.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Proof of combinations
  1. A proof (Replies: 3)

  2. Combinations -. (Replies: 4)

  3. Permutation combination (Replies: 11)

Loading...