Prove the claim $n! = \omega (2^n)$.

Question

Prove the claim $n! = \omega (2^n)$. The definition of $\omega(g(n))$ is that for any positive constant $c > 0$, there exists a constant $n_0$ such that $0 \leq cg(n) < f(n)$ for all $n > n_0$. Here $f(n) = n!$ and $g(n) = 2^n$

To prove the claim I first show that for sufficiently large $n$ then $(n - 1)! > 2^n$.

Let's define a predicate $P(n) = (n - 1)! > 2^n$. We show that $P(n)$ holds for all $n \geq 6$ using induction. We first consider the base case. Let $n = 6$ then:

$P(n) = (n - 1)! > 2^n \implies P(6) = 5! > 2^6 = 120 > 64$

So the base case holds. Now let $n > 6$ and consider $P(n + 1)$ then:

$P(n + 1) = n! > 2^{n + 1} = n \cdot (n - 1)! > 2 \cdot 2^n$

Now since $P(n)$ holds then $(n - 1)! > 2^n$ and since $n \geq 6$ then $n > 2$ and so $P(n + 1)$ holds, $P(n) \implies P(n + 1)$. This means $P(n)$ holds for all $n \geq 6$.

So we have shown that $(n - 1)! > 2^n$ for all $n \geq 6$. We now consider the claim that $n! = \omega (2^n)$. This means that there exists some constant $n_0$ such that for all $n > n_0$ and any $c > 0$ the inequality $0 \leq c2^n < n!$ holds. We have proven that $(n - 1)! > 2^n$ for $n \geq 6$ and so we may conclude:

$n! = n(n - 1)! > n2^n$

For $n \geq 6$. Now let $c > 0$ be arbitrary. Since $n$ grows arbitrarily large for any $c$ we find $n$ such that $n > c$. So let $c < n$ then we may conclude:

$n(n - 1)! > n2^n > c2^n$

Now let $n_0 = c$ then we obtain:

$n! = n(n - 1)! > n2^n > n_02^n$

For all $n > n_0$. And so we conclude that $n! = \omega (2^n)$.

The solution I came up with is a bit long-winded. What could possible alternative approaches be? Is there perhaps a short proof by contradiction?

Also, if there are any errors with my approach it would be appreciated if these are pointed out.

Answer 1

It is an asymptotic statement, so we may assume that $n \geq 3$, say.

Note that $$ 0 \leq \frac{2^n}{n!} = 2 \prod_{j=3}^n \frac{2}{j} \leq \frac{9}{2} \Big(\frac{2}{3}\Big)^n. $$ Hence, $2^n/n! = o(1)$ as $n \to \infty$, which demonstrates that $n! = \omega(2^n)$, as $n \to \infty$.

Answer 2

Note that $$n!\geq 3^{n-2}.$$ This trivially holds for the cases $n\leq 2$ and for larger $n$ is follows fia induction, as $n!$ increases by a factor of $n\geq3$ while $3^{n-2}$ increases only by a factor $3$.

Now note that as $\frac{3}{2}>1$ we know that $\big(\frac{3}{2}\big)^n\to\infty$. So given $c>0$ take $n_0$ such that for all $n>n_0$ we have that $$\bigg(\frac{3}{2}\bigg)^n\geq9c.$$ Then we have for all $n>n_0$ $$ 0<c2^n\leq3^{n-2}\leq n!\,, $$ i.e. $n!=\omega(2^n)$.