1. Not finding help here? Sign up for a free 30min 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!

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)!}
    [/tex]


    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, ?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: If b | a!(n-a)! can one say b | n!
  1. Is (a,b) open in R^n (Replies: 2)

  2. Lim a(n)b(n) = AB (Replies: 2)

Loading...