Proving inequality $3^{n^2} > (n!)^4$

Question

Prove that $3^{n^2} > (n!)^4$ for all positive integers $n$.

I tried to use induction on this problem but failed to do so. I instead tried to prove $3^{2n+1}>(n+1)^4$, but couldn't come up with the solution.

Answer 1

The induction-step should be pretty easy:

• Assume $\displaystyle3^{n^2}>(n!)^4$

• Prove $\displaystyle3^{(n+1)^2}>(n+1)!^4$:

  • $\displaystyle3^{(n+1)^2}=3^{n^2+2n+1}$

  • $\displaystyle3^{n^2+2n+1}=3^{n^2}3^{2n+1}$

  • $\displaystyle3^{n^2}3^{2n+1}>(n!)^43^{2n+1}$

  • $\displaystyle(n!)^43^{2n+1}=\frac{(n+1)!^4}{(n+1)^4}3^{2n+1}$

  • $\displaystyle\frac{(n+1)!^4}{(n+1)^4}3^{2n+1}=(n+1)!^4\frac{3^{2n+1}}{(n+1)^4}$

So all you have left to prove by induction is $3^{2n+1}>(n+1)^4$:

• Assume $\displaystyle3^{2n+1}>(n+1)^4$

• Prove $\displaystyle3^{2(n+1)+1}>(n+2)^4$:

  • $\displaystyle3^{2(n+1)+1}=3^{2n+3}$

  • $\displaystyle3^{2n+3}=3^{2n+1}3^2$

  • $\displaystyle3^{2n+1}3^2>(n+1)^43^2$

  • $\displaystyle(n+1)^43^2=9(n^4+4n^3+6n^2+4n+1)$

  • $\displaystyle9(n^4+4n^3+6n^2+4n+1)=9n^4+36n^3+54n^2+36n+9$

  • $\displaystyle9n^4+36n^3+54n^2+36n+9>n^4+8n^3+24n^2+32n+16$

  • $\displaystyle n^4+8n^3+24n^2+32n+16=(n+2)^4$

Answer 2

Clearly, $n^n > n!$ for $n>1$ and so $n^{4n} > (n!)^4$. Therefore, we only need to prove that $3^{n^2} \ge n^{4n}$, or equivalently, $3^n \ge n^4$. This is true for $n \ge 8$. For $n <8$, we just verify explicitly that $3^{n^2} > (n!)^4$.