Do factorials really grow faster than exponential functions? [closed]

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

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 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

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 7

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

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

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 10

Although it is too late to answer this question, especially, when really nice answers have already been presented, I want to share my intuition about the subject.

Suppose a sequence of positive integers is given: $1, 2, \cdots, n$, and you take geometric mean of the given numbers. As new numbers are added to the lot, the geometric mean will of course keep growing larger and larger, right? This means that there is no constant $C$ such that $$(n!)^{1/n} < C.$$ This means, for any constant $C$ we have $$n! > C^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$$.

Answer 12

Assume that $x>a>0$. Then: $$\frac{x!}{a^x}=\frac{a!\Pi^x_{i=a+1}i}{a^x}>a!\frac{(a+1)^{x-a}}{a^x}=\frac{a!}{(a+1)^a}\frac{(a+1)^x}{a^x}=\frac{a!}{(a+1)^a}(1+\frac{1}{a})^x\to_{x\to\infty}\infty$$

Answer 13

$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$