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

[alec_tronn]

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

Homework Statement

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

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!

 

[quasar987]

You probably meant (kn)! and not (kn!).

 

[quasar987]

just a tought: have you tried induction? You will have to use induction on k first, and then on n.

 

[jjou]

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.

 

[HallsofIvy]

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.

 

[Defennder]

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.

It should be 2^2 = 4, which does divide 24.

 

[HallsofIvy]

Oh, blast!

 

[alec_tronn]

just a thought: have you tried induction? You will have to use induction on k first, and then on n.

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?

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.

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!