3
$\begingroup$

I want to prove that the factorial grows faster than the exponential function. First, I introduce the ratio $$L = \frac{n!}{e^n}.$$ Then, I introduce another ratio : $$\frac{(n+1)!}{e^{n+1}} = \frac{(n+1) \cdot n!}{e \cdot e^n} = \frac{(n+1)}{e} L.$$ When the value of $n$ take values bigger and bigger and $L$ gets bigger and bigger. In other words, $$\lim_{n \to \infty} \frac{(n+1)}{e} = \infty,$$ meaning that $L$ is divergent. Thus $n!$ grows faster than the exponential.

$\endgroup$
1
  • 2
    $\begingroup$ Yes, your idea is exactly right, but you need to give $L$ a better name, which depends on $n$ (like $L_n$). $\endgroup$
    – hunter
    Nov 27, 2023 at 23:34

2 Answers 2

4
$\begingroup$

$$ \frac{n!}{e^n} = \prod_{i=1}^n\frac{i}{e}. $$ Since $$ \lim_{i \to \infty} \frac{i}{e} = \infty, $$ clearly the factorial is growing faster than the exponential.

$\endgroup$
0
$\begingroup$

Yes, your method shows specifically that $n!=\omega(e^n)$, since $L_n\to\infty$. There is nothing special about $e$ here, so you can use the same idea to show that $n!=\omega(\alpha^n)$ for any $\alpha$ (or to put it another way, $n!=\omega(e^{\beta n})$ for any $\beta$).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .