Do factorials really grow faster than exponential functions?

Question

Having trouble understanding this. Is there anyway to prove it?

Answer 1

If you're not quite in the market for a full proof:

$$a^n=a\times a\times a\times a...\times a$$ $$n!=1\times 2\times 3\times 4...\times n$$

Now what happens as $n$ gets much bigger than $a$? In this case, when $n$ is huge, $a$ will have been near some number pretty early in the factorial sequence. The exponential sequence is still being multiplied by that (relatively tiny) number at each step, while $n!$ is being multiplied by $n$. So even if $n!$ starts out small, it'll eventually start being multiplied by gigantic numbers at each step, and quickly outgrow the exponential. If $a=10$ and $n=100$, then $a^n$ has around $100$ digits, while $n!$ has over $150$ digits. Note that near $n=100$, $n!$ is having roughly 2 digits added per step (and that rate will only increase), while $a^n$ is still only ever going to get one more with every step. No contest.

Answer 2

Let me give a Hint: Let $f(n) = \dfrac{n! }{ a^n}$, for $ a > 1$. What is $\dfrac{f(n+1)}{f(n)}$??

Answer 3

An intuitive way to see this is to consider that you're trying to show $$a^n < n!$$ for sufficiently large $n$. Take the log of both sides, you get $$n\log(a) = \log(a^n) < \log(n!) = \sum_{i = 1}^n\log(i).$$ Now as you increase $n$ you only add $\log(a)$ to the left side, but the $\log(n + 1)$ that you add to the right can be arbitrarily large as $n$ becomes large. This can be made rigorous, but I think that it's intuitively clear that eventually it gets large enough to make up the difference and be greater than $n\log(a)$.

Answer 4

Substitute n! with Stirling's approximation, then divide ${a}^{n}$ with it and find the limit.

Answer 5

To explain it more precisely, $n!$ grows very fast when compared to a power $n$. Because the greater number is multiplied with the product each time: $$(n+1)!=1 \cdot 2 \cdots n \cdot (n+1).$$ But in case of exponential function, $$a^{n+1} = a \cdot a \cdots a,$$ the term $a$ remains constant.

Answer 6

Use the striling's approximation to $n!$ for large numbers we get,
$$ \log(n!)=n \log n -n. $$ also we have $$\log(a^n)=n\log a.$$ Now divide the equations we get, $$ \frac{\log(n!)}{\log(a^n)}=(n \log n -n)/n\log a. $$ $$ \frac{\log(n!)}{\log(a^n)}=\log n/\log a-1/\log(a). $$ for large a (a>1) we can neglect the term $1/\log(a)$. Hence we have, $$ \frac{\log(n!)}{\log(a^n)}\approx\log n/\log a $$ Hence , for $n>a$, $n!$ is higher. and for for $n<a$, $a^{n}$ is higher.

Answer 7

Why does the function $exp(x)$ converge?

Since

$$\exp(x)=\sum_{i=0}^{\infty} \frac{x^{n}}{n!}$$ for large $n$, $x^n$ grows slowly compared with $n!$.

Answer 8

Another possibility is to use the ratio test. Then, it's easy to make the argument rigorous and to get a sense of the relative sizes of $a^n$ and $n!$. Let $x_n = a^n/n!$, then

$$\frac{x_{n+1}}{x_n} = \frac{a^{n+1}}{(n+1)!}\frac{n!}{a^n} = \frac{a\,a^n}{a^n}\frac{n!}{(n+1)n!} = \frac{a}{n+1}.$$

Since the limit of this term is zero, it follows that, for any $r>0$, there is an $N\in\mathbb N$ such that $x_{n+1}<r x_n$ for all $n\geq N$. As a result, for $n>N$,

$$x_n < r^{n-N} x_N$$

so that $x_n$ approaches zero faster than $r^n$.

Answer 9

A simple visual with no fancy proof.

Let $n = 100$.

$2^n = 2\times2\times2\times2\times2\times2\times\dots \times 2$ <-- the 100th "$2$"

$n! = 1 \times2\times3\times4\times5\times6\times\dots\times 100$

See above after the 4th multiplication $2^n$ (i.e., $2^4$) = $16$ and $4! = 24$ and then you can see for the remaining operations that $n!$ is multiplying a greater number than $2^n$ is every time.

$\begin{array}{ccccccccccccc}2^n &=& 16& \times &2\times&2\times&2\times&2\times&2\times&\dots \times & 2 \times &2 \times & 2\\ n! &= & 24 &\times &5\times&6\times&7\times&8\times&9 \times &\dots \times& 98 \times& 99 \times& 100 \end{array}$

Now, it should be easy to see how $n!$ grows much quicker, especially for large values. For small values, it won't always hold true that $n!$ is greater.

Answer 10

$n!> k^n$ if $n\ge ke$

try it for yourself with various combinations of $n$ and $k$

use $\log(n!)$ and $k \log(n)$ for large $n$

Answer 11

We show that $$\lim_{n \to \infty} \frac{\displaystyle\sum_{1 \leq i \leq n}\log(i)}{n \log(a)} = \infty.$$ Indeed, $$\sum_{1 \leq i \leq n}\log(i) > \sum_{n/2 \leq i \leq n}\log(i).$$ Note that for all $i \geq n/2$, we have $\log(i) \geq \log(n/2) = \log(n)-1$. Hence, we have $\sum_{n/2 \leq i \leq n}\log(i) \geq \frac{n}{2}\log(n) - \frac{n}{2}$. Therefore, $\sum_{1 \leq i \leq n}\log(i) > \frac{n}{2}\log(n) - \frac{n}{2}$. It is clear that $$\lim_{n \to \infty} \frac{\frac{n}{2}\log(n) - \frac{n}{2}}{n\log(a)} = \lim_{n \to \infty}\frac{\log(n)}{2\log(a)} - \frac{1}{2\log(a)} = \infty$$.