2
$\begingroup$

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}

$\endgroup$
  • 2
    $\begingroup$ You don't seem to understand what $n!=O(2^n)$ means. What do you think it means? $\endgroup$ – whacka Sep 14 '14 at 0:11
  • $\begingroup$ 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. $\endgroup$ – TwilightSparkleTheGeek Sep 14 '14 at 0:14
  • $\begingroup$ 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! $\endgroup$ – whacka Sep 14 '14 at 0:19
  • $\begingroup$ 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. $\endgroup$ – TwilightSparkleTheGeek Sep 14 '14 at 0:23
  • $\begingroup$ Go back and reread the definition of $n!=O(2^n)$. $\endgroup$ – whacka Sep 14 '14 at 0:26
0
$\begingroup$

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$).

$\endgroup$
  • $\begingroup$ Stirling's is probably a bad idea pedagogically. One can easily show that $2^n/n!\to0$ though... $\endgroup$ – whacka Sep 14 '14 at 0:22
  • $\begingroup$ 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. $\endgroup$ – TwilightSparkleTheGeek Sep 14 '14 at 0:25
  • $\begingroup$ @Twilight I am thinking much, much more basic than calculus tools. $\endgroup$ – whacka Sep 14 '14 at 0:26
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – TwilightSparkleTheGeek Sep 14 '14 at 1:41
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Sep 14 '14 at 5:47
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.