# Need help understanding a step in an induction proof

I want to prove that $$(n!)^{(n-1)!}$$ divides $$n!!$$ via induction. I was going through a post I found on Quora doing this, but I got hung up on the last step. For the sake of legibility I'll rewrite the proof here:

Base step: $$n=1$$: $$1!^{(0!)} = 1$$, which divides $$1!! = 1$$.

Inductive step: Assume that $$k!! = a(k!)^{(k-1)!}$$ where $$a$$ is an integer. We want to show that $$b$$ is an integer where $$(k+1)!! = b(k+1)!^{k!}$$. Using this we have:

$$(k+1)k! * ((k+1)!-1) * \cdots * ((k+1)! -m) * k!! = b * (k+1)!^k! * k! * k!^{(k-1)!}$$

where $$(k+1)!-m-1 = k!$$ (since $$k!$$ is the first term in $$k!!$$), so $$m = (k+1)! - k! - 1$$.

Since $$k!! = a * k!^{(k-1)!}$$:

$$(k+1)k! * ((k+1)!-1) * \cdots * ((k+1)! -m) *a = b * (k+1)!^{k!} * k!$$ So: $$(k+1)*((k+1)!-1) *\cdots * ((k+1)!-m) *a = b * (k+1)!^{k!}$$

Now it can be seen that the value of $$m$$ is greater than or equal to the value of $$k!$$. Hence b is also an integer.

The bold statement is what I don't understand. Why is this stated now and not when we had $$m$$ and (more importantly) why does $$m \ge k!$$ imply that $$b$$ is an integer? Is it because there are more terms in the LHS than the RHS (after the RHS is multiplied out)? Even so, how can we guarantee that the LHS divides the RHS?

Thank you very much!

• I think you mean $(k!)!$ not k!!.$The double factorial$k!!$is something different. As to the argument, I don't follow it either. He seems to be saying that$(k+1)!\$ divides each of the terms on the LHS, but I don't see how that can be true. – saulspatz Dec 24 '18 at 2:05

$$m = (k+1)!-k!-1$$ $$=k!(k+1-1)-1$$ Thus $$k!(k-1)\le k!(k)-1