Induction proof [ little-o notation ]

Question

I have to prove that $ 2^n = o(n!) $, that is, $ \forall c \gt 0 \quad \exists$ $ n_0 \in \mathbb N$ such that $ \forall n \ge n_0$ we have $ 2^n \lt c.n! $

Well, this is what I did so far:

First I proved, by induction in $n$, that $ 2^n \lt c.n! $ (considering $c = 1$ and $ n_0 = 4$).

Then I proved, by induction in $c$, that $ 2^n \lt c.n! $ (considering $c \gt 1$ and $ n_0 = 4$).

Now I got stuck trying to prove for $0 \lt c \lt 1$. (I tried to consider $c$ as $\frac1m $ and prove by induction for $m \gt 1$)

Anyone can help me?

Thanks in advance.

Answer 1

Sufficient to check $2^n/n!\rightarrow 0$ as $n\rightarrow\infty$. Observe that $\sum_{n=0}^\infty2^n/n!=e^2$, so the series $2^n/n!$ converges uniformly. Thats it.

Answer 2

Here's another way to look at this problem. We can write $$ \frac{2^n}{n!} = \frac{2}{n}\left(\frac{2}{n-1}\cdot\frac{2}{n-2}\cdots\frac{2}{3}\right)\cdot\frac{2}{2}\cdot\frac{2}{1} $$ Now each factor in the parenthesized part is strictly less than $1$ so we have $$ \frac{2^n}{n!} < \frac{2}{n}\cdot\frac{2}{1}= \frac{4}{n} $$ Let $c>0$ be an arbitrary real. For that $c$ we'll have $4/n < c$ if and only if $n>(4/c)$ so we can take $\lceil4/c\rceil + 1$ to be your $n_0$ and we're done, having satisfied the conditions of the problem statement.