# Prove little o with just the definition

I have been searching for a while now but couldn't find anything about this exact pair of functions with the little $$\mathcal{o}$$ notation.

Given the functions $$f(n) = 2^{n}$$ and $$g(n) = n!$$ I am supposed to prove, or disprove, the following statement: $$f(n) \in \mathcal{o}(g(n))$$.

I am fairly sure that it's true but now I need an idea of how to show this. We have just started out with this whole concept and this is the second exercise, the first one being a relatively easy big $$\mathcal{O}$$ task. But this exercise is just beyond me right now. The only definition I am allowed to use (meaning: NO LIMITS) is $$\mathcal{o}(g(n)) = \{f(n)|\forall C > 0 \exists n_{0} \forall n\geq n_{0}:f(n) < C * g(n)\}$$. This means other than with big $$\mathcal{O}$$, where it suffices to show that there's at least one pair $$C$$ and a $$n_{0}$$ so that $$f(n) \leq C * g(n)$$ $$\forall n \geq n_{0}$$, I now have to prove that for every $$C > 0$$, there is such a $$n_{0}$$ so that the condition stated in the set is true.

I first have been thinking about the functions, and I would have an answer for $$\mathcal{O}$$, because you can prove with induction that $$2^{n} < n!, \forall n\geq 4$$. Meaning my C would be 1 here. However, I have no idea how to prove it for every C and would be grateful for any guidance! (It would already help to know how to start. Probably like, let $$C$$ be greater 0, and then I have to show that for any Value of this $$C$$, there is... because... My biggest struggle is to find meaningful estimations to get a chain of inequalities.)

• Try using Sterling’s approximation. – prime_hit May 19 '20 at 20:52
• $2\cdot2\cdot2\cdot2\lt1\cdot2\cdot3\cdot4$ and $\underbrace{2\cdot2\cdots2}_{n-5\ 2\text{'s}}\lt5\cdot6\cdots n-1.$ So for $n\ge5$, $\underbrace{2\cdot2\cdots2}_{n \ 2\text{'s}}\lt1\cdot2\cdot3\cdot4\cdot5\cdot6\cdots(n-1)\cdot 2= n!/(n/2)$ – John L. May 20 '20 at 0:32

Pick $$n_0 = \max\{ -\log c, 10 \}$$. Then, for all $$n \ge n_0 \ge 10$$: $$2^n = \frac{4^n}{2^n} \le \frac{4^n}{2^{n_0}} \le \frac{4^n}{1/c} = c \cdot (4^{n-10} \cdot 4^{10}) < c \cdot (4^{n-10} \cdot 10!) \le cn!$$

One way to prove $$f(n) = o(g(n))$$ is to prove that:

\begin{align*} \lim_{n \to \infty} \frac{f(n)}{g(n)} &= 0 \end{align*}

In this case, you know that:

\begin{align*} \lim_{n \to \infty} \frac{2^n}{n!} &= 0 \end{align*}

since the series for $$e^x$$ converges for all $$x$$, so it converges for $$x = 2$$, and the terms of a convergent series have limit 0.

Or, if you take $$n \ge 2$$, you see that:

\begin{align*} \frac{2^n}{n!} &= \frac{2}{1} \cdot \frac{2}{2} \cdot \frac{2}{3} \dotsm \frac{2}{n} \end{align*}

Each successive factor after the second is smaller than 1, so the infinite product diverges to 0. That is, you can write for $$n \ge 2$$:

\begin{align*} 0 &\le \frac{2^n}{n!} \le \frac{2}{1} \cdot \frac{2}{2} \cdot \left(\frac{2}{3} \right)^{n - 2} \end{align*}

As $$n \to \infty$$, the right hand side tends to 0.

• The OP wanted a proof with quantifiers, probably as exercise – HEKTO May 20 '20 at 2:59

$$2^n$$ is the product of n numbers which are all equal to 2.

n! is the product of n numbers from 1 to n.

Once n ≥ 3, if you increase n by 1, $$2^n$$ is doubled, while n! is multiplied by 4 or more. So basic maths shows that for n ≥ 3, $$n! ≥ 6/64 \cdot 4^n$$.

Given any C > 0 from the definition, you calculate how large n would have to be to make $$2^n < 6/64 \cdot 4^n$$.