# How to prove ${a_n} = \frac{n!}{2^n}$ diverges to $+ \infty$?

I would like to prove that the sequence ${a_n} = \frac{n!}{2^n}$ diverges to $+ \infty$. As I understand it, this means that for all numbers $M$, I must find a number $N$ such that for all $n \ge N$, I get $a_n \ge M$. However, I'm not sure how to pick $N$. Thanks.

-

You can use a lower bound on $n!$ instead of $n!$ itself. For example, when $n \ge 3$, $a_n = \frac{n!}{2^n} = \frac{2}{2^n}(3\cdot \ldots \cdot n) \ge \frac{2}{2^n}(3^{n-2}) = \frac{1}{2}\left(\frac{3}{2}\right)^n$. Since the sequence $\left(\frac{3}{2}\right)^n$ goes to $+\infty$, $a_n$ must also go to $+\infty$.

If you wish to go all the way back to the definition, you only need to elaborate the last sentence. This can be done as follows.

Note that now we know that $a_n \ge \frac 12\left(\frac 32\right)^n$ for $n \ge 3$. For any given $M > 0$, pick $N$ such that $\frac 12\left(\frac 32\right)^N = M$. (More specifically, $N = \frac{\log(2M)}{\log(3/2)}$.) If $N < 3$, we pick $N = 3$ instead. Then, for all $n > N$, we know $a_n \ge \frac 12\left(\frac 32\right)^n > M$.

-

$1$. Using induction, prove that $n! > 3^n$ for $n > 6$.

$2$. Hence, $\dfrac{n!}{2^n} > \left(\dfrac32 \right)^n$ for $n>6$.

$3$. Now prove that $\left(\dfrac32 \right)^n \to \infty$ as $n \to \infty$.

$4$. Conclude that $\dfrac{n!}{2^n} \to \infty$ as $n \to \infty$.

-

Note that if $k\ge 4$, then $\frac{k}{2}\ge 2$. It follows that if $n \ge 4$, then $$\frac{n!}{2^n} \ge \frac{6}{8} 2^{n-3}=\frac{6}{64}2^n.$$ The rest should be straightforward.

-

We will be using this result

Theorem 1: If ${a_n}$ be a sequence such that $\lim_{n\to \infty} \frac{a_{n+1}}{a_n}= a\,,$ then

1) if $|a|<1$, then $\lim_{n\to \infty}a_n =0 \,,$

2) if $a>1$, then $\lim_{n\to \infty}|a_n| =\infty \,.$

Now, we have $$\lim_{n\to \infty} \frac{a_{n+1}}{a_n}= \frac{(n+1)!}{2^{n+1}}\frac{2^n}{n!}=\frac{n+1}{2}=\infty,$$

which implies, by part $(2)$ of the theorem, $a_n$ diverges.

-
@AntonioVargas: Thanks for the comment. It is already corrected. –  Mhenni Benghorbal Jan 21 '13 at 19:33

Take

$$a_n:=\frac{2^n}{n!}\Longrightarrow \frac{a_{n+1}}{a_n}=\frac{2^{n+1}}{(n+1)!}\frac{n!}{2^n}=\frac{2}{n+1}\xrightarrow [n\to\infty]{}0$$

As $\,\{a_n\}\,$ is positive, the above (Ratio or D'alembert's Test) shows the infinite series $\,\displaystyle{\sum_{n=1}^\infty a_n}\,$ converges , so

$$a_n=\frac{2^n}{n!}\xrightarrow [n\to\infty]{}0\Longleftrightarrow \frac{n!}{2^n}\xrightarrow [n\to\infty]{}\infty$$

Note that instead $\,2\,$ we can take any positive real number and the result is the same

-

Look at the numbers. You've got $1!/ 2^0, 2!/2^2, 3!/2^3, 4!/2^4 ....$

Or $$\frac{1}{1}, \frac{1\cdot2}{2\cdot2}, \frac{1\cdot2\cdot3}{2\cdot2\cdot2}, \frac{1\cdot2\cdot3\cdot4}{2\cdot2\cdot2\cdot2}, \frac{1\cdot2\cdot3\cdot4\cdot5}{2\cdot2\cdot2\cdot2\cdot2}, ...$$

Or $1/1, 2/4, 6/8, 24/16, 120/32$ ....

After a while, they get bigger and bigger.

Looking at the second way of writing them, you can see that to get from one to the next, you multiply by: $2/2, 3/2, 4/2, 5/2$ .....

If all you want to prove is that the series blows up, you're done.

After a while, you get the next number by more-than-doubling.

If you keep doubling any number, It'll get as large as you like eventually. And your series gets bigger faster than that.

-