Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

It recently came to my mind, how to prove that the factorial grows faster than the exponential, or that the linear grows faster than the logarithmic, etc...

I thought about writing: $$ a(n) = \frac{k^n}{n!} = \frac{ k \times k \times \dots \times k}{1\times 2\times\dots\times n} = \frac k1 \times \frac k2 \times \dots \times \frac kn = \frac k1 \times \frac k2 \times \dots \times \frac kk \times \frac k{k+1} \times \dots \times \frac kn $$ It's obvious that after k/k, every factor is smaller than 1, and by increasing n, k/n gets closer to 0, like if we had $\lim_{n \to \infty} (k/n) = 0$, for any constant $k$.

But, I think this is not a clear proof... so any hint is accepted. Thank you for consideration.

share|improve this question
1  
This is similar to this question. –  robjohn Nov 9 '11 at 8:18
    
Your idea is clearly right, though it may be even mo rigor. –  Ilya Nov 9 '11 at 9:48
2  
$\frac{k^n}{n!} = \frac k1 \cdot \frac k2 \cdots \cdot \frac kk \cdot \frac k{k+1} \cdots \frac kn = k^k\frac 11 \cdot \frac 12 \cdots \cdot \frac 1k \cdot \frac k{k+1} \cdots \frac kn \leq k^k \frac{k}{n}$ –  N. S. Nov 9 '11 at 15:32

8 Answers 8

up vote 4 down vote accepted

If you know that this limit exists, you have $$ \lim_{n \to \infty} \frac{k^n}{n!} = \lim_{n \to \infty} \frac{k^{n+1}}{(n+1)!} = \lim_{n \to \infty} \frac k{n+1} \frac{k^n}{n!} = \left(\lim_{n \to \infty} \frac k{n+1} \right) \left( \lim_{n \to \infty} \frac {k^n}{n!} \right) = 0. $$ Can you think of a short way to show the limit exists? (You need existence to justify my factoring of the limits at the end. If you don't have that then there's no reason for equality to hold.)

share|improve this answer
3  
You need to justify the last part by proving that $\dfrac{k^n}{n!}$ is a bounded sequence. –  Asaf Karagila Nov 9 '11 at 8:09

The series for $e^k$ $$ \sum_{n=0}^\infty\frac{k^n}{n!} $$ converges by the ratio test. The terms of a convergent series must tend to $0$.


For $n\ge2k$, the ratio of terms is $\frac{k^{n+1}/(n+1)!}{k^n/n!}=\frac{k}{n+1}<\frac{1}{2}$. We can remove the reference to series (which seems to have bothered someone) with the following sandwich, valid for $n\ge2k$: $$ 0\le\frac{k^n}{n!}\le\frac{k^{2k}}{(2k)!}\left(\frac{1}{2}\right)^{n-2k} $$ which shows that $\displaystyle\lim_{n\to\infty}\frac{k^n}{n!}=0$.

share|improve this answer
4  
I would very much suspect that the OP asks because he did not yet prove that. –  Asaf Karagila Nov 9 '11 at 8:20
    
The ratio test, as with any test for convergence, only need hold for the tail of the series. For $n>2k$, the ratio of terms is $\frac{k^{n+1}/(n+1)!}{k^n/n!}=\frac{k}{n+1}<\frac{1}{2}$. –  robjohn Nov 9 '11 at 10:06
3  
Would the downvoter care to explain? –  robjohn Nov 9 '11 at 13:10
    
I suspect it might be one of the other answerers... –  The Chaz 2.0 Nov 9 '11 at 14:26
    
@TheChaz: may be the case –  Ilya Nov 9 '11 at 14:42

Your proof is clear to me. $k$ is fixed, so the right hand side of your equation, for $n>k$, has the form $$ {k\over n}\cdot\underbrace{{k\over n-1}\cdot{k\over n-2}\cdots{k\over k}}_{<1}\cdot C< {k \over n}\cdot C\rightarrow 0 $$

share|improve this answer

Probably not the kind of solution you're looking for, but just for fun:

It's easy to show that $\frac{n!^{1/n}}{n} \to e^{-1}$ as $n \to \infty$. (For example, write $\int_0^1 \log t\: dt$ as a limit of Riemann sums on the partitions $0,1/n,2/n, \dots, 1))$.

Thus, by the root test,

$$\sum_{n=0}^\infty \frac{k^n}{n!}$$

converges. Hence $\lim_{n \to \infty} \frac{k^n}{n!} = 0$.

share|improve this answer
    
Isn't it too much to use Riemann integrals and root test for such problems? Moreover, using $\int_0^1\log t\mathrm dt$ requires the knowledge if its value. –  Ilya Nov 9 '11 at 10:33
1  
Of course it is. Hence the disclaimer! –  Bruno Joyal Nov 9 '11 at 16:02
1  
I love the "just for fun" part of the question :P –  Patrick Da Silva Nov 10 '11 at 21:03

As @robjohn has mentioned, this question is indeed very similar to Prove that $\lim \limits_{n \to \infty} \frac{2^n}{n!} = 0$ the only question is who to play the role of $7$ in our case ($7$ is the smallest number for which $7!>(2+1)^7$ ). The general proof is the following: let us prove first that for any $j\in\mathbb N$ it holds that $n!\geq j^n$ for all $n$ large enough.

  1. First, let us put $N = j^2+j$, then $$ \frac{N!}{j^N} = \underbrace{\frac1j\cdot\frac2j\cdot\dots\cdot\frac jj}_{\pi_1}\cdot\underbrace{\frac{j+1}{j}\cdot\dots\cdot\frac{j^2}j}_{\pi_2}\cdot\underbrace{\frac{j^2+1}{j}\cdot\dots\cdot\frac{j^2+j}j}_{\pi_3}. $$ Now, $\pi_2\geq 1$ since all terms in the product are grater than $1$. Moreover, by multiplying correspondent terms $$ \pi_1\pi_3 = \frac{j^2+1}{j^2}\cdot\frac{2(j^2+2)}{j^2}\cdot\dots\cdot\frac{j(j^2+j)}{j^2}\geq1 $$ hence $N!\geq j^N$.

  2. For all $n\geq N$ it clearly holds now that $n!\geq j^n$. By induction: it holds for $n=N$. If it holds for some $n$ then $$ (n+1)!\geq n!\cdot n\geq j^n\cdot n\geq j^{n+1} $$ since $n\geq N\geq j$.

We proved that for any $j\in\mathbb N$ there is $N(j)$ s.t. $n\geq N(j)\Rightarrow n!\geq j^n$. Now let us put $j=[k]+1$, then $$ 0\leq\lim\limits_{n\to\infty}\frac{k^n}{n!}\leq \lim\limits_{n\to\infty}\left(\frac k{[k]+1}\right)^n = 0. $$

share|improve this answer
    
I didn't downvote myself, but this answer is one example of how you can do things the complicated way and it still works but is not nice to read. It's still good to see sometimes that there are long paths and short paths. –  Patrick Da Silva Nov 10 '11 at 21:02

Of course, one can break out the ratio test to show that the series $\sum\limits_{n=1}^\infty \frac{k^n}{n!}$ converges (absolutely) and hence $\lim\limits_{n\rightarrow\infty}\frac{k^n}{n!}=0$.

However, we don't have to use nuclear weapons. Clearly, $a_n=\frac{k^n}{n!}$ is bounded below by zero. If $n\geq k$ (or, if $k$ isn't an integer, $n\geq \lceil k \rceil$), we have

$a_{n+1}=\frac{k^{n+1}}{(n+1)!}=\frac{k^n}{n!}\frac{k}{n+1}<\frac{k^n}{n!}=a_n$.

So, since the sequence $\{a_n\}$ is eventually decreasing and bounded below, it converges.

To show that it converges to zero, you can now use Patrick Da Silva's method above.

share|improve this answer
1  
Filling the blanks I intentionally left blank? Aww, how sweet of you. =P Hehe good work. –  Patrick Da Silva Nov 10 '11 at 21:05

Here is another observation. Fix $k$. Since you are trying to find the limit as $n\to \infty$ you may assume that $n > k$. Then you have

$$ \frac{k^n}{n!} = \frac k1 \cdot \frac k2 \cdots \cdot \frac kk \cdot \frac k{k+1} \cdots \frac kn = c \frac k{k+1} \cdots \frac kn$$

where $c = k^k/k!$ is a constant independent of $n$. Next, for $1\leq i \leq n-k$ we have

$$\frac{k}{k+i} \leq \frac{k}{k+1}.$$

Therefore

$$c \frac k{k+1} \frac k{k+2} \cdots \frac kn \leq c \underbrace{\frac k{k+1} \frac{k}{k+1}\cdots \frac{k}{k+1}}_{n-k \text{ times}} = \left(\frac{k}{k+1}\right)^{n-k}.$$

What would you try next?

share|improve this answer

Let's observe an example :

$$\frac{9^n}{n!}$$ so we have that :

$$\frac{9^1}{1!}=9 , \frac{9^2}{2!}=40.5 , \frac{9^3}{3!}=121.5$$

but...

$$\frac{9^9}{9!}=\frac{9^8\cdot 9}{8! \cdot 9}=\frac{9^8}{8!}$$

and further...

$$\frac{9^{10}}{10!}=\frac{9^9\cdot 9}{9! \cdot 10} < \frac{9^9}{9!}$$

So we may conclude: after we throw out the first $k-1$ elements that sequence starts to decrease , therefore sequence :

$$\frac{k^n}{n!}$$

is decreasing if we set $ n\geq k$ , so we may conclude that :

$$n \rightarrow \infty \Rightarrow \frac{k^n}{n!} \rightarrow 0$$

share|improve this answer
7  
sequence $\frac12+\frac1n$ is decreasing as well. does it converge to $0$? –  Ilya Nov 9 '11 at 9:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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