108
$\begingroup$

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

$\endgroup$
7
  • 3
    $\begingroup$ Check out the chapter "$\pi$ is irrational" in Spivak's Calculus; he offers a neat little proof in the form that $\frac{a^n}{n!} < \epsilon $ for all sufficiently large $n$. In my 3rd edition copy its on pg. 308. $\endgroup$ Apr 5, 2013 at 21:29
  • 1
    $\begingroup$ Below n=4, the exponential grows faster. above n=4 the factorial grow faster. $\endgroup$
    – User3910
    Jul 22, 2018 at 21:30
  • 1
    $\begingroup$ what a great question!! Liked it.. $\endgroup$
    – Vicrobot
    Sep 8, 2018 at 21:09
  • 5
    $\begingroup$ So this guy asked a question with absolutely no details and has 106 upvotes. But when I ask a question with every relevant information but it misses a few things then everyone votes for delete and almost gives me a million downvotes.(OMG,just notices that the question is 8 years old, but the ingenious community only closed this question 3 years ago).WHATEVER, ...EVERYONE UPVOTED IT, SO LET ME UPVOTE IT TOO!! $\endgroup$ Mar 14, 2021 at 18:12
  • 1
    $\begingroup$ @Vicrobot, truly lovely. $\endgroup$ Mar 14, 2021 at 18:12

13 Answers 13

240
$\begingroup$

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.

$\endgroup$
10
  • 61
    $\begingroup$ While this is not proof, this is I think the most intuitive answer. $\endgroup$
    – Benoit
    Apr 5, 2013 at 8:50
  • 4
    $\begingroup$ @Benoit: All one needs to do to make it a proof is divide both numbers into two parts--the product of the first a terms, and the product of everything else, yielding [for n>a] (a!)(n-a)! and (a^a)(a^(n-a)). n! is larger than a^n any time (n-a)!/(a^(n-a)) is larger than (a^a)/(a!). The latter expression is constant, and the former expression is always at least ((a+1)/a)^(n-a)), which will clearly grow to be larger than any finite bound. $\endgroup$
    – supercat
    Apr 5, 2013 at 15:57
  • 9
    $\begingroup$ Another intuition is that $n! = 1\times 2\times\ldots\times n$ is a "cousin" of $n^n = n\times n\times\ldots\times n$. $\endgroup$
    – Kaz
    Apr 5, 2013 at 18:53
  • 14
    $\begingroup$ @bubba An argument requires rigor to be a proof. Some people are convinced that magnetic bracelets enhance their "energy" and well-being. Of course, it's okay (nay, useful) to have a clear, less-than-a-proof argument for something that is actually true. $\endgroup$
    – Kaz
    Apr 6, 2013 at 7:57
  • 3
    $\begingroup$ @CMCDragonkai $n^n$ grows faster. $n^n=n\times n\times n\times n\cdots$, while $n!=n\times(n-1)\times(n-2)\times(n-3)\cdots$. The factors in $n!$ are all smaller, so $n^n$ will be bigger. It's "allowed" to be bigger because the fact that the base is growing as well lets it stay ahead of the factorial. $\endgroup$ Oct 12, 2014 at 0:03
145
$\begingroup$

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

$\endgroup$
3
  • 23
    $\begingroup$ nice and simple. $\endgroup$
    – Mitch
    Apr 6, 2013 at 1:19
  • 24
    $\begingroup$ @Mitch, Not really, for the non-math oriented... $\endgroup$
    – Pacerier
    Jun 25, 2014 at 21:44
  • 3
    $\begingroup$ @Pacerier well then we can say: "$a$ is fixed. $n$ grows larger. Will $n+1$ eventually grow larger than $a$? Since the ratio is positive but also $<1$ once $n+1>a$, then as $n$ further increases, what number will the ratio tend towards?" many questions, but straightforward nonetheless. The answer to the last question is also intuitive. $\endgroup$
    – Mr Pie
    May 23, 2020 at 12:45
61
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Depending on what the OP means by "grow faster", they may actually want to show that, for any $a$ and $c$, $ca^n < n!$ for sufficiently large $n$ (which, in particular, implies that $\lim_{n\to\infty} \frac{a^n}{n!} = 0$ for all positive $a$). Of course, the proof is basically the same, even with the extra factor of $c$ in front. $\endgroup$ Apr 5, 2013 at 15:38
  • 23
    $\begingroup$ I'm a tiny bit skeptical of an "intuitive" proof that starts with "Take logarithms" :P $\endgroup$ Apr 5, 2013 at 19:53
  • $\begingroup$ @BenMillwood there is nothing non-intuitive stuff in logarithms imho. The best anser - clean and strict. $\endgroup$ Oct 26, 2015 at 9:47
16
$\begingroup$

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

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

$\endgroup$
6
  • 18
    $\begingroup$ This is an enormous overkill... $\endgroup$
    – tomasz
    Apr 5, 2013 at 17:39
  • $\begingroup$ Why do you find it an overkill? $\endgroup$ Apr 5, 2013 at 18:26
  • 1
    $\begingroup$ Well, seeing that factorials grow a lot faster than exponentials can be done in a very simple argument, while proving Stirling's approximation is a rather arduous task. $\endgroup$
    – tomasz
    Apr 5, 2013 at 18:28
  • $\begingroup$ I wasn't talking about proving it, but rather using it, to replace n! with it. Then if you divide ${a}^{n}$ with $\sqrt{2\pi n}{({\frac{n}{e}})^{n}}$, you'll have once $\sqrt{2\pi n}$ in the denominator, and also $\frac{ae}{n}$ taken to the ${n}^{th}$ power. As both a and e are constants, $\frac{ae}{n}$ will be less than 1 (at least after a while), making its ${n}^{th}$ power also converge to 0. $\endgroup$ Apr 5, 2013 at 18:41
  • 14
    $\begingroup$ @DrH : "overkill" in math usually means using a very high-powered theorem to prove a more elementary result that can be proven in a much more contained, elementary way. This would qualify. (Not to say its wrong or anything, but it is in fact overkill). $\endgroup$ Apr 5, 2013 at 21:48
3
$\begingroup$

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

$\endgroup$
1
  • 3
    $\begingroup$ Might want to clarify that the ratio test is for series (Note that this may only make sense to those who know Calculus): $\displaystyle\sum_{n=0}^\infty \frac{a^n}{n!}$, is this convergent? Ratio test: let $\displaystyle x_n = \frac{a^n}{n!}$, then $\displaystyle\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}$ Therefore, since $\displaystyle\lim_{n\to\infty}\frac{a}{n+1} = 0$, $n!>a^n$ for large values of n. $\endgroup$
    – Justin
    May 16, 2013 at 23:39
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ To where is the limit? Infinity? If so add something like \lim_{x\righarrow \infty} $\endgroup$
    – Jeel Shah
    Feb 26, 2014 at 13:23
  • $\begingroup$ You lost me at log(n/2)=log(n)−1 $\endgroup$
    – Maude
    Sep 16, 2018 at 23:47
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ If you generalize $a$ from natural numbers to positive real numbers, it's enough to choose a natural number $b$ such that $x>b>a>0$. $\endgroup$
    – hat180
    Jun 10, 2016 at 16:20
-1
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.