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!

Homework Help: If b | a!(n-a)! can one say b | n!

  1. Nov 28, 2009 #1
    1. The problem statement, all variables and given/known data

    Suppose b | a!(n-a)! and prove that b | n!

    2. Relevant equations

    m | n <=> n = am

    3. The attempt at a solution

    b | a!(n-a)! ,so that
    a!(n-a)! = bs, so that
    a!(n-a)!(nCa) = bs(nCa) (nCa is a combinations of n items)
    n! = bs(nCa)
    And so b is obviously a divisor of n!
  2. jcsd
  3. Nov 28, 2009 #2
    We can show a!b! divides (a+b)!

    WLOG assume a > b,

    First, make the following observation,

    [tex] \frac{(a+b)!}{a!b!} = \frac{(a+b)(a+b-1) \ldots (b+1) b!}{a!b!} = \frac{(a+b)(a+b-1) \ldots (b+1)}{a!}[/tex]

    Now, by induction on b, if b=1,
    [tex] (a+b)! = (a+1)! = (a+1)a! = (a+1)a!b![/tex]
    So by definition we have that a!b! divides (a+b)!

    So assume the result holds for b, and we will show the result holds for b+1. Now, consider,

    [tex] \frac{(a+b+1)!}{a!(b+1)!} = \frac{(a+b+1)(a+b)(a+b-1) \ldots (b+1)!}{a!(b+1)!}

    Next, we will be a bit tricky by bracketing things off right.

    [tex] \frac{(a+b+1)(a+b)(a+b-1) \ldots (b+1)b!}{(b+1)!a!} = \frac{(a+b+1)b!(a+b)(a+b-1) \ldots (b+1)}{(b+1)!a!} [/tex]

    Now, it suffices to show the above is an integer. First let's consider what our inductive hypothesis tells us. It says that a! divides (a+b)(a+b-1) ... (b+1). So there is some integer d such that,

    [tex] \frac{(a+b)(a+b-1) \ldots (b+1)}{a!} = d [/tex]

    Now we have to show the following is an integer,but

    [tex] \frac{(a+b+1)b!}{(b+1)!} = \frac{(a + (b+1))b!}{(b+1)!} = \frac{ab! + (b+1)!}{(b+1)!}[/tex]

    Err, ?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook