2

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.

Hanul Jeon
  • 27,376
Reslley Gabriel
  • 89
  • 2
  • 8
  • Induction does not work for reals ($c$ in your case) only integers ($n$ in your case). – gt6989b Apr 18 '13 at 13:16
  • Thanks. I thought that proving for c and then proving for c+1 would prove for all c (real) in that interval. – Reslley Gabriel Apr 18 '13 at 13:27
  • No, induction only proves for integers. Think about it - if you prove $P_1$ and also that $P_n \implies P_{n+1}$ then together they imply $P_2$ and then $P_3, P_4, \ldots$. But nowhere did we prove $P_\pi$ or $P_{1.5}$, for example – gt6989b Apr 18 '13 at 13:31

2 Answers2

3

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.

Sunny
  • 221
0

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.

Rick Decker
  • 8,718
  • Thanks! But if we consider $n \gt 4/c$ we can't consider our $n_0$ as $\lceil 4/c \rceil$ because the statement says that $n \ge n_0 $, so $n$ may be equal to $n_0$. For example, choosing $c = 2$ our $n_0$ would be $\lceil 4/2 \rceil = 2$, and the statement $2^2 \lt 2 . 2!$ would be false. Am I wrong? – Reslley Gabriel Apr 18 '13 at 18:02
  • Good catch. Fixed. – Rick Decker Apr 19 '13 at 01:32