Thread: Proof that A^n < N!

1. Proof that A^n < N!

For any positive integer A, there is an integer N, which of course can vary depending on A, so that for all n >= N, A^n < n!.
How am I supposed to show this? Do I need to show A^n = Big-O of n! or use induction? I tried both and I can't seem to figure it out.

2. Re: Proof that A^n < N!

For $k > A^2$ what happens to $\frac{k!}{A^k}$ as $k$ increases?

3. Re: Proof that A^n < N!

I understand that n! increases at a faster rate than A^n, but how do I write that as a formal proof if I have to prove that n! increases at a faster rate? I tried doing a limit, but I can't use L'hopitals rule on the factorial because I can't use derivate (other than for log() and polynomials).

4. Re: Proof that A^n < N!

Ok. Suppose that $N > A^2$ and $\frac{N!}{A^N} = c$. Then for $n=N+k$

$\frac{n!}{A^n} = \frac{(N+k)!}{A^{N+k}} > \frac{N!A^{2k}}{A^N A^k} = \frac{N!}{A^N}A^k = cA^k$

For $A > 1$, the final expression above is clearly increasing without bound and so for all sufficiently large $k$ it is greater than 1.

You can do $A=1$ separately.

5. Re: Proof that A^n < N!

Thank you! This makes a lot of sense!!

6. Re: Proof that A^n < N!

Presumably you know calculus and the fact that for any A
$$e^A=\sum_{n=0}^{\infty}{A^n\over n!}$$
In particular,
$$\lim_{n\to\infty}{A^n\over n!}=0$$
So let $\epsilon=1$ in the definition of limit and you get that there exist $N$ such that for all $n\geq N$,
$${A^n\over n!}<1$$