Prove that $a^n$ is $O(n!)$.

Question

I proved by induction that $2^n = O(n!)$. Can this fact be used to prove the following:

Let $a$ be a positive constant and $n$ be a natural number. Show that $a^n=O(n!)$.

I have already written a proof that $2^n<n$! for all $n\geq4$ (or that $2^n$ is $O(n!)$). It goes like this:

==============

1. Basis: $2^4<4!$
2. $16<24$ is true

3. assume true for $k$

4. Prove for k+1

5. $2^k<k!$
6. multiply by two on both sides
7. $2\cdot2^k<2\cdot(k!)$
8. $2^{k+1}<2(k!)$
9. As $k>2$ must necessarily be greater than $2$, the following inequality is true: $2^{k+1}<(k+1)k!$
10. As there is no distinction between $(k+1) k!$ and $(k+1)!$ we can simplify to: $2^{k+1}<(k+1)!$ We see the theorem holds true for $k+1$, given that it is true for $k$.

==============

Intuitively, it seems to me that this should be somehow useful, but I cannot link the two together. Am I just wrong about that? I'm finding it a lot more difficult to write a proof for which is valid for an arbitrary number like $a.

Answer 1

Just prove that $\lim\limits_{n\to\infty}\frac{a^n}{n!} = 0$ for any $a>0$.

That's easy to see if you choose any $k\geq2a$, because then $\lim\limits_{n\to\infty}\frac{a^n}{n!}=\lim\limits_{n\to\infty}\frac{a^k}{k!}\frac{a^{n-k}}{(k+1)(k+2)\ \ldots\ n}\leq\frac{a^k}{k!}\lim\limits_{n\to\infty}\frac{a^{n-k}}{(2a)^{n-k}}=\frac{a^k}{k!}\lim\limits_{n\to\infty}\frac1{2^{n-k}}=\frac{a^k}{k!}\cdot0=0$

So you get even $a^n=o(n!)$ as $n\to\infty$.

Answer 2

Suppose that $$a^n \le M n!$$ We then can write that $$a^{n+1} \le M (n+1)!$$ as soon as $a\le {n+1}$.

So let us take $M = \max \{ \frac{a^n}{n!}, n\le a \}$. We know that:

• when $n\le a$, ${a^j}\le M{j!}$
• when $a\le {n+1}$, $a^n \le M n!$ by induction.