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

Question

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?

Answer 1

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)!$.

Answer 2

Hint: The product of $k $ consecutive integers is divisible by $k! $.

For proving the above statement, consider the coefficients in binomial expansion.

Answer 3

Hint: Every product of $m$ consecutive integers is divisible by $m!$. Let $m=4$.

Answer 4

Could proceed with induction:

n=1: $$ (4n)! = 4! = (4!)^n $$ n=2: $$ (4n)! = 8!= 8(7)(6)(5)(4)(3)(2)(1) \mbox{ is divisible by } (4!)^n = 4^2(3^2)(2^2)(1) $$ Induction step: Assume that $(4!)^{n-1}$ divides $(4(n-1))!$

n: $$ \frac{(4n)!}{(4!)^n} = \frac{(4(n-1))! \, \times \, \mathbf{(4n-3)(4n-2)(4n-1)(4n)}}{(4!)^{n-1} \, \times \, \mathbf{4!}}$$ Notice that bold parts divide eachother trivially, and the non-bold parts divide by the induction hypothesis

Answer 5

One can also use induction to show this. When $n =1$, the quotient is an integer$( = 1)$. Assume this is true for $n =k$ i.e., $(4k)!/(4!)^{k} \in \mathbb{Z}$. Then for $n =k+1$ we can see that $(4(k+1)!)/(4!)^{k+1} = \{(4k+4)(4k+3)(4k+2)(4k+1)(4k!)\}/4! \times (4!)^{k}$ Then we need to prove that $(4k+1)(4k+2)(4k+3)(4k+4)/4!$ is an integer, which is indeed as pointed out in above post.