4
$\begingroup$

I am having issues with this proof: Prove by contradiction that $n! \ne O(2^n)$. From what I understand, we are supposed to use a previous proof (which successfully proved that $2^n = O(n!)$) to find the contradiction.

Here is my working so far:

Assume $n! = O(2^n)$. There must exist $c$, $n_{0}$ such that $n! \le c \cdot 2^n$. From the previous proof, we know that $n! \le 2^n$ for $n \ge 4$.

We pick a value, $m$, which is gauranteed to be $\ge n_{0}$ and $\ne 0$. I have chosen $m = n_{0} + 10 + c$.

Since $m > n_0$:

$m! \le c \cdot 2^m\qquad (m > n \ge n_0)$

$\dfrac{m!}{c} \le 2^m$

$\dfrac{1}{c} m! \le 2^m$

$\dfrac{1}{m} m! \le 2^m\qquad (\text{as }m > c)$

$(m - 1)! \le 2^m$

That's where I get up to.. not sure which direction to head in to draw the contradiction.

  • 0
    The sentence starting, "from a previous proof..." has the inequality wrong.2012-07-29

7 Answers 7

1

In Factorial Inequality problem $\left(\frac n2\right)^n > n! > \left(\frac n3\right)^n$, they have obtained $ n!\geq \left(\frac{n}{e}\right)^n. $ Hence $ \lim_{n\rightarrow\infty}\frac{n!}{2^n}\geq\lim_{n\rightarrow\infty}\left(\frac{n}{2e}\right)^n=\infty. $ Suppose that $n!=O(2^n)$. Then there exist $C>0$ and $N_0\in \mathbb{N}$ such that $\frac{ n!}{2^n}\leq C $ for all $n\geq N_0$. Lettting $n\rightarrow\infty$ in the aobve inequality we obtain $ \lim_{n\rightarrow\infty}\frac{n!}{2^n}\leq C, $ which is an absurd.

1

It is quite easy to show that $n! \ge 3^n$ if $n\ge 7.$ If $n = 7$, we have $3^7 = 2187 < 5040 = 7!$. Now let $n\ge 7$.
$n! = n\cdot(n-1)! \ge 3\cdot(n-1)! = 3\cdot 3^{n-1}, $ if we invoke the induction hypothesis $n! \ge 3^n$.
Then ${n!\over 2^n} \ge {3^n\over 2^n} \to \infty$ as $n\to\infty$. This rules out $n! = O(2^n)$.

0

If $n!=O(2^n)$, then there is a constant $c$ such that whenever $n>N$, then

$n!\leq c\cdot 2^n$

This means that whenever $n>N$,

$\frac{n!}{2^n}\leq c$

This means that the sequence $a_n=\frac{n!}{2^n}$

is bounded.

Don't you smell something fishy? I give you $m=1234966785$. Can you find $n'$ such that $a_{n'}>m$? Can you do this for any $m$ I give you?

Note that

$a_n=\frac 1 2 \frac 2 2 \frac 3 2 \cdots \frac{n-1}{2}\frac n 2$

Note that each term, except $\frac 1 2 $ greater or equal than $1$ for $n=1,2,\dots$ that is

${a_n} = \frac{1}{2}\frac{2}{2}\frac{3}{2} \cdots \frac{{n - 1}}{2}\frac{n}{2} \geqslant \frac{1}{2}1 \cdot 1 \cdots 1 \cdot \frac{n}{2} = \frac{n}{4}$

Then, this means $b_n=\frac n 4 $ is bounded. Do you see what's going on?

0

Something "fancy" here. Look at the positive series $\sum_{n=1}^\infty \frac{2^n}{n!}$

Of course, we know the above series has sum equal to $\,e^2\,$ , but what's important here is that it is seriously easy to prove the convergence of the series and thus $\frac{2^n}{n!}\xrightarrow [n\to\infty]{} 0\Longrightarrow \frac{n!}{2^n}\xrightarrow [n\to\infty]{}\infty$ and thus it's obvious the sequence cannot be bounded...

0

Suppose $n! = O(2^n)$. Then there is an integer $N$ and a positive real $c$ such that $n! < c 2^n$ for $n > N$, or $r_n =\frac{2^n}{n!} > \frac1{c}$.

Let $M = \max(N, 4)$. If $n > M$, $r_{n+1} =\frac{2^{n+1}}{(n+1)!} =\frac{2}{n+1}\frac{2^n}{n!} < \frac12 r_n $. Therefore $r_{n+k} < \frac{r_n}{2^k}$.

Note: To show $\frac1{2^k} \to 0$, by Bernoulli's inequality, $2^n =(1+1)^n > n $.

-1

This is the cleanest proof I can think of:

Using the same techniques used to show $2^n=O(n!)$, we can show that $3^n = O(n!)$ as well. If we had $n!=O(2^n)$, then this implies $3^n = O(2^n)$, contradiction.