0

$1 < \log ⁡n < n < n\log ⁡n < n^2 < n^3< \ldots < 2^n < 3^n < 4^n < \ldots < n! < n^n$

I am trying to find out if $n!$ is greater than $4^{n}$. One way to attempt to solve this is to compare $n!$ with $4^{n}$ by taking a limit as $n$ approaches infinity, and for that, I would use the limit:

$$ \lim_{z\to \infty} \frac{n!}{4^{n}} $$

But to solve this limit, I needed to use L'Hôpital's Rule, by taking the derivative of both the numerator and the denominator.

However, I cannot directly differentiate $n!$ since it is a discrete function. To handle this, I used the Gamma function, which is a continuous function such that $\Gamma(n-1) = n!$

$$ \lim_{n\to \infty}\frac{\int_{0}^{\infty }t^{n-1}\cdot e^{-t}dt}{4^{n}} $$

However, I am having trouble finding an answer that indicates whether $n!$ grows faster than $4^{n}$ or not.

Could you help me? I'm not sure what strategy to use

Anton Vrdoljak
  • 2,717
rafaelcb21
  • 203
  • 3
    Just note that $n$ is larger than 5 for all $n>5$. =) or use a ratio test. Using the gamma function is overkill. – Michael Oct 06 '23 at 22:48
  • 2
    Another method for finding limits involving factorials like this is using Sterling's approximation. This may work nicely if the function in denominator is harder to bound. – chirpyboat73 Oct 06 '23 at 22:56
  • 1
    This problem doesn't need any calculus: it is easy to prove by induction (after a little calculation to find a base case). See the answer given by Darth Geek. – Rob Arthan Oct 06 '23 at 22:59

1 Answers1

4

Use induction on $n$. Prove the fact for some $n > 4$. Then $$4^{n+1} = 4\cdot 4^n < 4n! < (n+1)n! = (n+1)!$$

Darth Geek
  • 12,296
  • 1
    Indeed! It's obviously true by induction if it's ever true. You wrote up your answer while I was making sure that where was an $n$ for which it is true $\ddot{\smile}$. Is there a slicker way than brute force to see why there must be such an $n$? – Rob Arthan Oct 06 '23 at 22:57
  • Is the following way of reasoning correct for $4\cdot4^{n} < 4n!$ ? To $n > 4$, so the first digit of n is 5. So $4\cdot4^{5} = 4096$ and $4n! = (4\cdot5) \cdot (4\cdot4) \cdot (4\cdot3) \cdot (4\cdot2) \cdot (4\cdot1)$ or $4\cdot(5\cdot4\cdot3\cdot2\cdot1)$ – rafaelcb21 Oct 06 '23 at 23:33
  • 1
    Stirling's approximation tells you that $n! \sim (\frac ne)^n$, so I would look around $4e \approx 10$. In fact $9$ is enough – Ross Millikan Oct 07 '23 at 05:26
  • 1
    @rafaelcb21 You have to prove it for some $n > 4$ but it might not be true for all $n > 4$. As Ross Millikan pointed out, you have to go as far as $n = 9$ to prove it. – Darth Geek Oct 07 '23 at 12:54