86
$\begingroup$

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

$\endgroup$

closed as off-topic by user21820, Shaun, Sahiba Arora, Ethan Bolker, Parcly Taxel Feb 21 '18 at 13:25

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – user21820, Shaun, Sahiba Arora, Ethan Bolker, Parcly Taxel
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Related: math.stackexchange.com/questions/136626/… - in particular I prove that $(2k^2)! > k^{2k^2}$ for any $k$. $\endgroup$ – Ben Millwood Apr 5 '13 at 19:54
  • 2
    $\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$ – Coffee_Table Apr 5 '13 at 21:29
  • 1
    $\begingroup$ Below n=4, the exponential grows faster. above n=4 the factorial grow faster. $\endgroup$ – User3910 Jul 22 '18 at 21:30
  • 1
    $\begingroup$ what a great question!! Liked it.. $\endgroup$ – Vicrobot Sep 8 '18 at 21:09
  • $\begingroup$ See my answer here for a proof: stackoverflow.com/a/55301991/1519409 $\endgroup$ – inavda Mar 23 at 20:51

13 Answers 13

191
$\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$
  • 42
    $\begingroup$ While this is not proof, this is I think the most intuitive answer. $\endgroup$ – Benoit Apr 5 '13 at 8:50
  • 1
    $\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 '13 at 15:57
  • 8
    $\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 '13 at 18:53
  • 12
    $\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 '13 at 7:57
  • 2
    $\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$ – Robert Mastragostino Oct 12 '14 at 0:03
118
$\begingroup$

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

$\endgroup$
  • 14
    $\begingroup$ nice and simple. $\endgroup$ – Mitch Apr 6 '13 at 1:19
  • 16
    $\begingroup$ @Mitch, Not really, for the non-math oriented... $\endgroup$ – Pacerier Jun 25 '14 at 21:44
59
$\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$
  • $\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$ – Ilmari Karonen Apr 5 '13 at 15:38
  • 19
    $\begingroup$ I'm a tiny bit skeptical of an "intuitive" proof that starts with "Take logarithms" :P $\endgroup$ – Ben Millwood Apr 5 '13 at 19:53
  • $\begingroup$ @BenMillwood there is nothing non-intuitive stuff in logarithms imho. The best anser - clean and strict. $\endgroup$ – Alex Zhukovskiy Oct 26 '15 at 9:47
9
$\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$
8
$\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$
5
$\begingroup$

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

$\endgroup$
  • 14
    $\begingroup$ This is an enormous overkill... $\endgroup$ – tomasz Apr 5 '13 at 17:39
  • $\begingroup$ Why do you find it an overkill? $\endgroup$ – András Hummer Apr 5 '13 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 '13 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$ – András Hummer Apr 5 '13 at 18:41
  • 13
    $\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$ – Coffee_Table Apr 5 '13 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$
  • 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 '13 at 23:39
2
$\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$

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$
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$
  • $\begingroup$ To where is the limit? Infinity? If so add something like \lim_{x\righarrow \infty} $\endgroup$ – Jeel Shah Feb 26 '14 at 13:23
  • $\begingroup$ You lost me at log(n/2)=log(n)−1 $\endgroup$ – Maude Sep 16 '18 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$
  • $\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 '16 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.