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

• alec_tronn
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.
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!

Last edited:
You probably meant (kn)! and not (kn!).

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

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.

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.

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.

Oh, blast!

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!

## 1. 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.

## 2. 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).

## 3. 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.

## 4. 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.

## 5. 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.

• Calculus and Beyond Homework Help
Replies
6
Views
658
• Calculus and Beyond Homework Help
Replies
5
Views
711
• Calculus and Beyond Homework Help
Replies
12
Views
1K
• Calculus and Beyond Homework Help
Replies
9
Views
876
• Calculus and Beyond Homework Help
Replies
1
Views
573
• Calculus and Beyond Homework Help
Replies
3
Views
771
• Calculus and Beyond Homework Help
Replies
1
Views
744
• Calculus and Beyond Homework Help
Replies
9
Views
2K
• Calculus and Beyond Homework Help
Replies
6
Views
1K
• Calculus and Beyond Homework Help
Replies
3
Views
714