Prove for any positive integer $n$, $(4n)!$ is divisible by $2^{3n}\cdot 3^n$

binomial-coefficientscombinatoricsdiscrete mathematicsdivisibilityelementary-number-theory

Problem: Prove for any positive integer $n$, $(4n)!$ is divisible by $2^{3n}\cdot 3^n$

Solution given by the professor: $$4! = 2^3\cdot 3$$
$$(4!)^n = 2^{3n}\cdot 3^n$$
$$\frac{(4n)!}{(4!)^n}=\frac{(4n)!}{2^{3n}\cdot 3^n}$$

My question: The steps are pretty straightforward but I don't understand the last and most crucial step. For $\frac{(4n)!}{2^{3n}\cdot 3^n}$ to be an integer, we need $(4!)^n$ to divide $(4n)!$, is it a clear property of the factorial? How is it obvious?

Best Answer

It is true that $(4!)^n\mid(4n)!$, but it is not obvious (at least, not to me). You can use the fact that, for any natural number $m$, $4!\mid m(m+1)(m+2)(m+3)$; after all$$\frac{m(m+1)(m+2)(m+3)}{4!}=\binom{m+3}4.$$So:

  • $4!\mid1\times2\times3\times4$;
  • $4!\mid5\times6\times7\times8$;
  • $\vdots$
  • $4!\mid(4n-3)\times(4n-2)\times(4n-1)\times(4n)$

and therefore $(4!)^n\mid(4n)!$.