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.
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!)\,.$