# Prove/disprove $n! = O(2^n)$ via mathematical induction

My computer science professor has us tasked with proving or disproving the statement $$n! = O(2^n)$$. We are then supposed to say if it's always true, always false, or non-conclusive (true in some cases but false in other cases).

So I believe that the statement $$n! = O(2^n)$$ is non-conclusive for the sole reason that it isn't true until $$n\geq4$$. I'm having a hard time proving the inductive step of my mathematical induction. Below is what I have so far, could someone help me out figure the induction step?

Problem $$\boldsymbol 1$$(c) Is the statement True, False, or non-conclusive? Non-conclusive meaning true in some cases but false in other cases.

Question. $$C(n) =n!$$ implies that $$C(n) =O(2^n)$$ $$\longleftarrow$$ Prove or disprove

Given: $$2^n \leq n!$$

For $$n=1$$, we have $$2^1 \leq 1! \implies 2\leq1$$ which is FALSE.
For $$n=2$$, we have $$2^2 \leq 2! \implies 4\leq2$$ which is FALSE.
For $$n=3$$, we have $$2^3 \leq 3! \implies 8\leq6$$ which is FALSE.
For $$n=4$$, we have $$2^4 \leq 4! \implies 16\leq24$$ which is TRUE.

From pluging in some values we see that $$n!$$ seems to grow faster than $$2^n$$. Let's try and prove that through mathematical induction.

Let us suppose the following property $$P(n)$$ defined thusly: $$2^n \leq n! \quad \text{for all integers } n \geq 4.$$

Mathematical Induction Proof:

Step $$1$$. Prove the Basis step, we must show $$P(4)$$ is true. $$P(n) =2^n \leq n! \longrightarrow 2^4 \leq 4! \implies 16 \leq 24,$$ which is true.

Step $$2$$. Prove the inductive step, now suppose this works for any integer $$k$$, $$k \leq 4$$ such that $$2^k \leq k! \longleftarrow \text{inductive hypothesis}$$

Now to complete mathematical induction proof, we must show that the following is true for $$P(k+1)$$: \begin{align} 2^{k+1} &\leq (k+1)! \\ (2^k)(2) &\leq (k+1)(k!) \end{align}

• You don't seem to understand what $n!=O(2^n)$ means. What do you think it means? – whacka Sep 14 '14 at 0:11
• BigOh intuitively means that in this case n! grows at a rate equal or at most 2^n. The statement is trying to claim that n! grows at most 2^n which I know to be false since n! grows way faster than any exponential function based on the graph/chart in my computer science textbook. – TwilightSparkleTheGeek Sep 14 '14 at 0:14
• Your intuition is fairly good. But proving $2^n<n!$ is not enough to disprove $n!=O(2^n)$. Do you understand why it's not enough? You need to understand what $n!=O(2^n)$ means! – whacka Sep 14 '14 at 0:19
• Nope, I don't understand why it's not enough. Honestly, I think it's enough, but have no means to back my statement up. Please teach me, whacka. :) This is quite frankly my first exploration in proof, this is an introduction to algorithm's class I'm taking. Maybe I don't really understand the meaning thoroughly then, there are holes in my understanding I won't lie. – TwilightSparkleTheGeek Sep 14 '14 at 0:23
• Go back and reread the definition of $n!=O(2^n)$. – whacka Sep 14 '14 at 0:26

Hint: Stirling's approximation tells you $\log n! = n \log n - n + O(\log n)$ or that $n! \sim \sqrt{n} \left( n / e \right)^n$ where $\sim$ neglects a constant.

Alternatively, assume $n! \in O(2^n)$. Then there would exists a constant $0 < k < \infty$ such that $n! \leq k 2^n$. Show something goes wrong with this for n larger than some $N$ (which is in terms of $k$).

• Stirling's is probably a bad idea pedagogically. One can easily show that $2^n/n!\to0$ though... – whacka Sep 14 '14 at 0:22
• whacka, I know of L'Hopital's rule and that it can be used to prove that n! factorial grows faster than 2^n, but I'm not allowed to use that. Batman, I don't know about Stirling's approximation. – TwilightSparkleTheGeek Sep 14 '14 at 0:25
• @Twilight I am thinking much, much more basic than calculus tools. – whacka Sep 14 '14 at 0:26

Outline: Divide $1\cdot 2\cdot 3\cdot 4\cdot 5\cdots n$ by $2\cdot 2\cdot 2\cdot 2\cdots 2$. Since $\frac{4}{2}\ge 2$ and $\frac{5}{2}\ge 2$ and so on, for $n\ge 3$ the ratio is $\ge \frac{3}{2}2^{n-3}$.

If one feels like it, one can do this more formally by induction. The inequality holds at $n=3$, and the induction step is easy.

• How is this relevant to my question? It looks nothing like the factorial and neither is the ratio. I might not be up to par yet with all this proof business, it seems. :/ So this can be done by induction, huh? :D – TwilightSparkleTheGeek Sep 14 '14 at 1:41
• The relevance is that it is a complete solution to the problem, and shows that $n!$ is not big $O(2^n)$, In fact it shows that $2^n/n!$ approaches $0$ as $n\to\infty$, that $n!$ grows much faster than $2^n$. The product $1\cdot 2\cdots n$ is $n!$. You had the essence of the argument, but did not quite see that it did the job. – André Nicolas Sep 14 '14 at 5:47

The statement $n! = O(2^n)$ means that there is a positive $c$ and a positive integer $N$ such that $n! \le c 2^n$ for $n \ge N$, or $r(n) =\frac{n!}{2^n} \le c$ for $n \ge N$.

Choosing $n \ge \max(N, 4)$, $r(n+1) =\frac{(n+1)!}{2^{n+1}} =\frac{n+1}{2}\frac{n!}{2^n} >2r(n)$. By induction, $r(n+k) > 2^k r(n)$ or $r(n) <r(n+k)/2^k < c/2^k$.

Therefore $r(n)$ can be made arbitrarily small, which is a contradiction.