$d>0$ Prove $ d^n =O(n!)$

Question

To solve this question , I came up below kinda solution: $ d^n $ $\leq n!$

$\frac{d^n}{n!} \leq$ constant

But how am I prove this. By the way this is Big Oh Notation

Answer 1

You need to use proof by induction, choosing a suitable constant. $d^n$ is $O(n!)$ if there is a constant $c$ such that $d^n \le cn!$ for large enough $n$.

Choose the constant $c = d^d$.

Base case. For all $n\le d$, $d^n \le c n!$ because $c=d^d$ and $d^n\le d^d, \forall n\le d$

Induction case. Assume for some $k>d$, $d^k \le ck!$. Multiply both sides by $d$ to get $d^{k+1} \le cdk!$, but $d<k<k+1$, so $cdk! \le c(k+1)k! = ck!$. Hence $d^{k+1} \le (k+1)!$.