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!

  • 1
    $\begingroup$ 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. $\endgroup$ – 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<k!(k)$$

So since m is bounded below by a positive multiple of k! it will be greater than or equal to k!.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.