Dominating Big-O

Question

How could I prove that $O(5^n)$ is dominated by $O(n!)$ by using induction?

Or: $5^n \in O(n!)$

I've got the basic formulas written out in regards to $f(k+1)$ but I'm just not sure how to proceed.

Answer 1

Hint:

Set $u_n=\dfrac{5^n}{n!}$ and use the ratio test to show that $5^n=o(n!)$. A fortiori, $5^n=O(n!)$.

Answer 2

There is no need to use induction here. Just notice that for $n \geq 5$ all but we have that all but the first $4$ factors in $n!$ are at least $5$. Therefore $n! > 4! \cdot 5^{n-4} = \frac{24}{5^4} \cdot 5^n$. So there is an $n_0$ and a $c$ such that $5^n \leq n!$ whenever $n \geq n_0$.