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

  • Thread starter alec_tronn
  • Start date
In summary, the proof of (kn)! being divisible by (n!)^k appears to be almost completed, but a flaw in the reasoning prevents it from being a factor.
  • #1
alec_tronn
29
0
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!
 
Last edited:
Physics news on Phys.org
  • #2
You probably meant (kn)! and not (kn!).
 
  • #3
just a tought: have you tried induction? You will have to use induction on k first, and then on n.
 
  • #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.
 
  • #5
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.
 
  • #6
HallsofIvy said:
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.
 
  • #7
Oh, blast!
 
  • #8
quasar987 said:
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?




jjou said:
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!
 

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

What does it mean for (kn) to be divisible by (n)^k?

When (kn) is divisible by (n)^k, it means that the result of the division is a whole number without any remainder. In other words, (n)^k is a factor of (kn) and the quotient is an integer.

How can you show that (kn) is divisible by (n)^k?

To show that (kn) is divisible by (n)^k, you can use mathematical induction. Start by proving the statement for the base case (k=1) and then assume it is true for (k=n) and prove it for (k=n+1). This will prove that the statement is true for all positive integers (k).

Can you provide an example to demonstrate that (kn) is divisible by (n)^k?

Yes, for example, if we let n=3 and k=2, then (kn) = (3*2) = 6 and (n)^k = (3^2) = 9. We can see that 9 is a factor of 6, as 6 divided by 9 gives a quotient of 0 with a remainder of 6.

What is the significance of (kn) being divisible by (n)^k?

The fact that (kn) is divisible by (n)^k has many practical applications in mathematics and science. It allows us to simplify complex equations and solve problems more efficiently. It also helps in understanding patterns and relationships between numbers.

Are there any exceptions where (kn) is not divisible by (n)^k?

Yes, there are exceptions where (kn) is not divisible by (n)^k. One example is when (n) is equal to 0, as any number multiplied by 0 will result in 0 and 0 is not divisible by any non-zero number. Another exception is when (k) is equal to 0, as any number raised to the power of 0 is equal to 1 and (kn) will not be divisible by 1 unless (n) is also equal to 1.

Similar threads

Back
Top