# Big - O Problem

Show that $a^n$ = O(n!) where a>0

I can see how it is true but I don't know how to work out the values for C and K in

$|f (x)| ≤ C|g(x)|$ whenever $x > k.$

I have been looking at this for ages so any help would be great.

-

We will give explicit expressions for $k$ and $C$, though that is not necessary for proving the result.

Assume that $a\gt 0$. Let $k=\lceil a\rceil$, and let $C=\dfrac{a^k}{k!}$. If $n \gt k$, then $$\frac{a^n}{n!}=\frac{a^k}{k!}\frac{a^{n-k}}{(k+1)(k+2)\cdots (n)}.$$

Note that each of the $n-k$ terms $k+1, k+2, \dots, n$ is greater than $k$, and hence greater than $a$. It follows that $$\frac{a^{n-k}}{(k+1)(k+2)\cdots (n)}\lt 1.$$ So we are going downhill from $k$ on, and conclude that if $n\gt k$, $$\frac{a^n}{n!} \lt \frac{a^k}{k!}=C,$$ and therefore $a^n\lt Cn!$.

Remark: A modification of the above argument shows that $\dfrac{a^n}{n!}$ has limit $0$. Just let $k=\lceil 2a \rceil$. Then past $k$ we are always multiplying by factors that are $\le \dfrac{1}{2}$, so we are going downhill fast. However big $C$ might be, after a while it will be dragged to $0$.

-

Use the fact that $\lim_{n\to \infty} \frac{a^n}{n!} = 0 \,,$, which implies that $a^n=O(n!)\,.$

-