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!

Show that (kn!) is divisible by (n!)^k ?

  1. Feb 3, 2008 #1
    Show that (kn)! is divisible by (n!)^k ?

    1. The problem statement, all variables and given/known data
    Show that (kn)! is divisible by (n!)^k.


    3. The attempt at a solution
    I attempted a factorization of the problem as follows:
    (kn)! = (kn)*(kn-1)*(k-2)...(kn-n+1) *
    ((k-1)n-1)*((k-1)n-2)*((k-1)n-1)...((kn-1)n-n+1)*
    ((k-2)n-1)*((k-2)n-2)*((k-2)n-1)...((kn-2)n-n+1)*
    .
    .
    .
    ((k-k+1)n-1)*((k-k+1)n-2)*((k-k+1)n-1)...((k-k+1)n-n+1)

    Then, I wanted to factor that into: (k!)(n!)^k... which I now realize is illegal. I feel like I'm close or headed in the right direction? Any advice? Thanks a lot!
     
    Last edited: Feb 3, 2008
  2. jcsd
  3. Feb 3, 2008 #2

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You probably meant (kn)! and not (kn!).
     
  4. Feb 3, 2008 #3

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    just a tought: have you tried induction? You will have to use induction on k first, and then on n.
     
  5. Feb 3, 2008 #4
    Show that (kn)! is divisible by (n!)^k.

    An idea:

    First, for n: Clearly n^k divides (kn)! since n, 2n, 3n, ..., kn will give you (k!)*(n^k).
    Similarly, for any integer a < n, we have ka < kn and thus a, 2a, 3a, ..., ka will give you (k!)*(a^k).
    So each of (2^k), (3^k), (4^k), ..., ((n-1)^k), and (n^k) are factors of (kn)!.

    It looks like the proof is almost finished, but you have to show that these factors don't "overlap." Or rather, for n > 3, overlapping is inevitable, so you have to find a way around that.

    Don't know if this is the right path.
     
  6. Feb 3, 2008 #5

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Here's another idea: if n= k= 2, then (kn)!= 4!= 24 while (n!)^k= 2^4= 16. And 24 is NOT divisible by 16.
     
  7. Feb 3, 2008 #6

    Defennder

    User Avatar
    Homework Helper

    It should be 2^2 = 4, which does divide 24.
     
  8. Feb 3, 2008 #7

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Oh, blast!!
     
  9. Feb 3, 2008 #8
    I'm not sure induction would be of much use here unless I knew the algebraic sequence to go through to make the two sides equal. But it did give me a little more insight...

    I tried to do the first couple k's, so that I'd have a base case to start from:

    k=1, (kn)! = (1n)! which is obviously divisible by (n!)^1

    k=2, (kn)! = (2n)! = (2n)(2n-1)(2n-2)(2n-3)(2n-4)(2n-5)(2n-6)(2n-7)(2n-8).....
    = 2(n)(2n-1)2(n-1)(2n-3)2(n-2)(2n-5)2(n-3)(2n-7)2(n-4).....
    = (2^n)(n!)(2n-1)(2n-3)(2n-5)(2n-7)...

    I feel like I found a pattern... if I can find another n! in this, maybe I can generalize and all would be good and well?





    I'm not exactly following you... because when you put that all together you get ((k!)^n)*((n!)^k), which as far as I can tell isn't a factor of the original (kn)! Am I missing something terribly obvious here?

    Thanks for everyone's help!!!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Show that (kn!) is divisible by (n!)^k ?
  1. K|n!+k from k=2,3,4 .n (Replies: 10)

Loading...