Inductive Proof?

Question

Prove that (k!)^n divides (kn)! for all k and n where both k and n are natural numbers. (kn is the product of k and n)

Here are we supposed to fix either k or n and then use induction on the other? How to handle this question?

Answer 1

First prove this is true for n = 1

(k*1)! mod (k!)^1 = 0

This is obvious since they both equal k!

Now we must show that

if (kn)! mod (k!)^n = 0 then (k(n+1))! mod (k!)^(n+1) = 0

I'm working on it:

Preliminary facts:

1. P(a + b) = a!(P(a+b,b))

2. P(n,k) mod k! = 0 because P(n,k)/k! = C(n,k) which is always a whole number

Proof:
The n= 1 case is proven. Now I assume:
3. (kn)! mod (n!)^k = 0 for some n in N.

Now I show that this implies:
4. (k(n+1))!mod(k! ^(n+1)) = 0

By #1 above:
(k(n+1))! = (kn+k)! = (kn)!P(kn,k)

With algebra:
k! ^(n+1) = k! (k!)^n

so now I rewrite
(kn)!P(kn,k) mod k! (k!)^n = 0

By #2 above I know that:
P(kn,k) mod k! = 0

So the only possible way to get a remainder is for
(kn)!/ (k!)^n to leave a remainder, but assumption #3 tells me it does not. Thus #3 implies #4 and the theory is proven for all Natural Numbers.

Answer 2

I will use the fact that aCb = "a choose b" = a!/(b!(a-b)!) is always an integer for all a>=b. Then I will induct over n.

Base case: n=1, true since k! divides itself.

Inductive Hypothesis: Assume (k!)^n divides (kn)! for n=j, now we have to use this to prove it is true for n=j+1.

(k!)^(j+1) = k! * (k!)^j, since we know by our assumption that (k!)^j divides (kj)!, we know that k! * (k!)^j divides k!*(kj)!. Then since k(j+1) choose k is an integer, we know that k! * (kj)! divides [k(j+1)]!. So we are done!